Submission #15385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15385	2015-07-12T07:00:41 Z	ainta	통로 위의 개미 (kriii3_X)	C++	0 / 85	11 ms	6336 KB

X

#include<stdio.h>
#include<algorithm>
using namespace std;
struct SegTree{
    SegTree *c1, *c2;
    int S;
    SegTree(){
        c1=c2=NULL;
        S=0;
    }
};
int L, Q, cnt, P[201000], SS[201000], Rank[201000];
struct Query{
    int b, e;
}w[5];
void AddQ(int b, int e){
    if(b<0)b+=2*L,e+=2*L;
    b%=(2*L),e%=(2*L);
    if(b>e)e+=2*L;
    if(e>=2*L){
        w[cnt].b=b,w[cnt].e=2*L-1;cnt++;
        w[cnt].b=0,w[cnt].e=e-2*L;cnt++;
        return;
    }
    w[cnt].b=b,w[cnt].e=e;cnt++;
}
SegTree *Root, *Root2;

void Ins(SegTree *nd, int b, int e, int x, int y){
    if(b==e){
        nd->S+=y;
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1=new SegTree(), nd->c2=new SegTree();
    if(x <= m)Ins(nd->c1,b,m,x,y);
    else Ins(nd->c2,m+1,e,x,y);
    nd->S=0;
    if(nd->c1)nd->S += nd->c1->S;
    if(nd->c2)nd->S += nd->c2->S;
}

int Gap(SegTree *nd, int b, int e, int s, int l){
    if(b==s&&e==l){
        return nd->S;
    }
    int m = (b+e)>>1, r = 0;
    if(nd->c1 && s <= m)r += Gap(nd->c1,b,m,s,min(m,l));
    if(nd->c2 && l > m)r += Gap(nd->c2,m+1,e,max(m+1,s),l);
    return r;
}

int Num;

int Pro(int mid, int t){
    int s = 0;
    cnt = 0;
    if(mid < L){
        AddQ(-t,-t+mid);
        AddQ(2*L-mid-t,2*L-t);
    }
    else if(mid > L){
        AddQ(-t,-t+2*L-mid);
        AddQ(-t+mid,-t+L*2);
    }
    else AddQ(0,2*L-1);
    s=0;
    for(int i=0;i<cnt;i++){
        s += Gap(Root,0,2*L-1,w[i].b,w[i].e);
    }
    return s;
}

int main(){
    int i, be, ed, mid, r, bb, ee;
    long long t;
    int p;
    int a, b;
    scanf("%d%d",&L,&Q);
    Root = new SegTree();
    Root2 = new SegTree();
    while(Q--){
        scanf("%lld%d%d",&t,&p,&a);
        t%=(2*L);
        if(p==1){
            scanf("%d",&b);
            if(b == -1)a = 2*L-a;
            if(a < L)bb = a+1, ee = 2*L-a-1;
            else if(a > L)bb = 2*L-a+1, ee = a-1;
            else bb = -1;
            Num++;
            Rank[Num] = Pro(a,t)+1;
            a=(a-t+2*L)%(2*L);
            P[Num] = a;
            Ins(Root, 0, 2*L-1, a, 1);
            SS[Num] = Gap(Root2, 0, 2*L-1,0,a);
            cnt = 0;
            if(bb == -1)continue;
            bb=(bb-t+2*L)%(2*L);
            ee=(ee-t+2*L)%(2*L);
            AddQ(bb, ee);
            for(i=0;i<cnt;i++){
                Ins(Root2, 0,2*L-1,w[i].b,1);
                if(w[i].e+1<=2*L-1)Ins(Root2, 0,2*L-1,w[i].e+1,-1);
            }
        }
        if(p==2){
            be = 0, ed = L-1, r = L;
            a = Gap(Root2,0,2*L-1,0,P[a])+Rank[a]-SS[a];
            while(be<=ed){
                mid=(be+ed)>>1;
                if(Pro(mid,t) >= a){
                    r= mid;
                    ed=mid-1;
                }
                else be=mid+1;
            }
            printf("%d\n",r);
        }
    }
}

Subtask #1

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	6336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-