POI Ice Skates (BOJ 8177번)

문제는 https://www.acmicpc.net/problem/8177 링크에서 풀어볼 수 있다.

 

문제 설명: 초기에 1~n 크기의 신발들이 각각 k쌍 씩 있다. 그리고 신발의 크기가 r인 사람은 r~r+d 크기의 신발을 신을 수 있다. 이때, m개의 상황이 생기는데, 각각의 상황은 2가지 종류 중 하나이다. (1) 신발 크기가 $r_i$인 사람 $x_i$ 명이 온다. (2) 신발 크기가 $r_i$인 사람 $x_i$명이 나간다. (당연하지만 안 들어온 사람은 못 나간다.) 들어오는지 나가는지는 $x_i$의 부호로 구별할 수 있다. 각각의 상황이 발생했을 때, 현재 있는 모든 사람에게 위 조건을 만족하도록 신발을 분배할 수 있는지 여부를 묻는 문제이다. (들어오는 사람에게 신발을 주는 개념이 아니라 상황이 발생할 때마다 최대한 위 조건을 만족시키도록 처음부터 재분배하는 개념이다.)

 

변수 조건: (1≤n≤200,000, 1≤m≤500,000, 1≤k≤$10^9$, 0≤d <n) 단 $r_i$, $x_i$는 (1≤$r_i$≤n-d, $-10^9$≤$x_i$≤$10^9$)

 

문제풀이: 문제 조건을 적당히 이리저리 처리해보면 신발 크기가 i인 사람의 수를 저장하는 배열 p[i]에서 k를 뺸 배열에서의 최대 연속합이 d*k를 초과하지 않아야 한다는 것을 알 수 있다. 따라서 이를 세그먼트 트리로 O(log n)만에 배열의 최대연속합을 구하고 이것이 d*k를 초과하는지 여부로 출력을 하면된다.

배열 p[i]-k에서 매 구간의 최대연속합은 다음 3개중 하나이다. i) 왼쪽 절반구간에서의 최대값 ii) 오른쪽 절반구간에서의 최대값 iii) 왼쪽 절반구간의 접미사 합 값의 최대값 + 오른쪽 절반구간의 접두사 합 값의 최대값. 각각 구간에서의 최대값, 총합, 접미사 합 최대값, 접두사 합 최대값을 배열에 저장해 세그먼트 트리 쿼리 처리하듯이 구해주면 된다. 따라서 시간복잡도 O(m*log n).

 

시행착오와 했던 생각: 처음 문제 보았을때, 뭔가 딱 전형적인 쿼리 문제로 O(n$log{}$m) 느낌이 났다. 또, log 형식 쿼리니 세그먼트 트리 구성하면 될것 같았다. 또, 문제조건 처리하는 것 까지는 문제가 없었는데 하... $r_i$≤n-d 조건을 보지 못하고 저부분을 이상하게 처리해주다가 WA가 많이 나왔다. 또, 중간에 구간 max를 그 구간의 전체합이라고 착각하고 코드를 짜서 틀려버렸다.. 문제를 항상 정확히 읽고, 더 많이 풀어보면서 구현실수랑 짜는데 걸리는 시간을 줄여야겠다.

 

풀이 코드: 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll n,m,k,d;
ll lf[800006],rg[800006],ar[200005],tree[800006],sum[800006];
 
ll getupd(ll l,ll r,ll nd,ll c)
{
    if(r<c||c<l) return tree[nd];
    if(l==r&&l==c)
    {
        lf[nd]=ar[l],rg[nd]=ar[l],sum[nd]=ar[l];
        return tree[nd]=ar[l];
    }
    ll md=(l+r)>>1,ret=-1e17;
    ll candl=getupd(l,md,nd*2,c),candr=getupd(md+1,r,nd*2+1,c);
    sum[nd]=sum[nd*2]+sum[nd*2+1]; 
    lf[nd]=max(sum[nd*2]+lf[nd*2+1],lf[nd*2]);
    rg[nd]=max(sum[nd*2+1]+rg[nd*2],rg[nd*2+1]);
    ret=max(ret,candl),ret=max(ret,candr);
    ret=max(ret,rg[nd*2]+lf[nd*2+1]);
    return tree[nd]=ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>k>>d;
    for(int i=1;i<=n;i++)
        ar[i]=-k,getupd(1,n,1,i);
    for(int i=1;i<=m;i++)
    {
        ll a,b;cin>>a>>b;
        ar[a]+=b;
        ll c=getupd(1,n,1,a);
        if(c>k*d) cout<<"NIE"<<"\n";
        else cout<<"TAK"<<"\n";
    }
    return 0;
}