oj.uz

Submission #15568

# Submission time Handle Problem Language Result Execution time Memory
15568 2015-07-12T23:56:20 Z ainta 통로 위의 개미 (kriii3_X) C++
30 / 85
 3000 ms 87124 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
struct SegTree{
    SegTree *c1, *c2;
    int S;
    SegTree(){
        c1=c2=NULL;
        S=0;
    }
};
long long L;
int cnt, n, Q;
struct Query{
    long long b, e;
}w[5];
void AddQ(long long b, long long 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;

void Ins(SegTree *nd, long long b, long long e, int x, int y){
    if(b==e){
        nd->S+=y;
        return;
    }
    int m = (b+e)>>1;
    if(x <= m){
        if(!nd->c1)nd->c1 = new SegTree();
        Ins(nd->c1,b,m,x,y);
    }
    else{
        if(!nd->c2)nd->c2 = new SegTree();
        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, long long b, long long e, long long s, long long l){
    if(b==s&&e==l){
        return nd->S;
    }
    long long 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 Pro(long long mid, long long t){
    long long s = 0;
    cnt = 0;
    if(mid < L){
        AddQ(-t,-t+mid);
        if(mid)AddQ(2*L-mid-t,2*L-t-1);
    }
    else if(mid > L){
        AddQ(-t,-t+2*L-mid);
        AddQ(-t+mid,-t+L*2-1);
    }
    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 Rank[601][1010], In[201000], SZ[601], MM;
int TP[201000];

void init(){
    int i, j, cnt = 0, pv = 1, tt;
    for(i=1;i<=MM;i++){
        for(j=1;j<=SZ[i];j++)TP[++cnt]=Rank[i][j];
        SZ[i]=0;
    }
    tt = (cnt-1)/600+1;
    for(i=1;i<=cnt;i++){
        if(SZ[pv] == tt)pv++;
        Rank[pv][++SZ[pv]] = TP[i];
        In[TP[i]]=pv;
    }
    MM = pv;
}

void UDT(int a, int r){
    if(!MM){
        MM++;
        Rank[1][++SZ[1]] = a;
        In[a] = 1;
        return;
    }
    int i, x, rr = r;
    for(i=1;i<=MM;i++){
        if(SZ[i]+1>=r)break;
        r-=SZ[i];
    }
    x = i;
    if(SZ[x] == 800){
        init();
        UDT(a,rr);
        return;
    }
    for(i=SZ[x];i>=r;i--)Rank[x][i+1]=Rank[x][i];
    Rank[x][r] = a;
    SZ[x]++;
    In[a] = x;
}

int Get(int a){
    int x = In[a], i, c = 0;
    for(i=1;i<x;i++)c+=SZ[i];
    for(i=1;i<=SZ[x];i++){
        if(Rank[x][i]==a)break;
    }
    return c+i;
}

int main(){
    int r, p, b;
    long long t,be, ed, mid;
    long long a;
    scanf("%lld%d",&L,&Q);
    Root = new SegTree();
    while(Q--){
        scanf("%lld%d%lld",&t,&p,&a);
        t%=(2*L);
        if(p==1){
            scanf("%d",&b);
            if(b == -1)a = 2*L-a;
            n++;
            UDT(n, Pro(a,t)+1);
            a=(a-t+2*L)%(2*L);
            Ins(Root, 0, 2*L-1, a, 1);
        }
        if(p==2){
            a = Get(a);
            be = 0, ed = L-1, r = L;
            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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5548 KB Output is correct
2 Correct 2 ms 5152 KB Output is correct
3 Correct 3 ms 5416 KB Output is correct
4 Correct 4 ms 5284 KB Output is correct
5 Correct 2 ms 5416 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 3 ms 5548 KB Output is correct
9 Correct 6 ms 5680 KB Output is correct
10 Correct 5 ms 5680 KB Output is correct
11 Correct 2 ms 5152 KB Output is correct
12 Correct 4 ms 5548 KB Output is correct
13 Correct 8 ms 5284 KB Output is correct
14 Correct 6 ms 5416 KB Output is correct
15 Correct 4 ms 5152 KB Output is correct
16 Correct 3 ms 5284 KB Output is correct
17 Correct 1 ms 5284 KB Output is correct
18 Correct 0 ms 5416 KB Output is correct
19 Correct 4 ms 5548 KB Output is correct
20 Correct 4 ms 5548 KB Output is correct
21 Correct 9 ms 5284 KB Output is correct
22 Correct 4 ms 5152 KB Output is correct
23 Correct 2 ms 5152 KB Output is correct
24 Correct 3 ms 5416 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 6868 KB Output is correct
2 Correct 535 ms 8980 KB Output is correct
3 Correct 1020 ms 6340 KB Output is correct
4 Correct 962 ms 8716 KB Output is correct
5 Correct 626 ms 32608 KB Output is correct
6 Correct 767 ms 43564 KB Output is correct
7 Correct 740 ms 35644 KB Output is correct
8 Correct 833 ms 56764 KB Output is correct
9 Correct 1533 ms 86992 KB Output is correct
10 Correct 1369 ms 86992 KB Output is correct
11 Correct 1445 ms 87124 KB Output is correct
12 Execution timed out 3000 ms 35380 KB Program timed out