oj.uz

Submission #15544

# Submission time Handle Problem Language Result Execution time Memory
15544 2015-07-12T09:24:22 Z ainta 통로 위의 개미 (kriii3_X) C++
30 / 85
 3000 ms 159200 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, Q, cnt;
int n;
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, long long x, long long y){
    if(b==e){
        nd->S+=y;
        return;
    }
    long long 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 = nd->c1->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){
    int 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[1001][710], In[201000], SZ[1001], MM, TP[201000];
int P[201000];

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

void UDT(int a, int r){
    if(!MM){
        MM++;
        Rank[1][++SZ[1]] = a;
        In[a] = 1,P[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] == 700){
        init();
        UDT(a,rr);
        return;
    }
    for(i=SZ[x];i>=r;i--){
        P[Rank[x][i]]++;
        Rank[x][i+1]=Rank[x][i];
    }
    Rank[x][r] = a;
    SZ[x]++;
    In[a] = x;
    P[a] = r;
}

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

int main(){
    int i, p, r;
    long long be, ed, mid;
    long long t;
    long long a;
    int b;
    scanf("%lld%lld",&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 8 ms 7268 KB Output is correct
2 Correct 0 ms 6344 KB Output is correct
3 Correct 5 ms 6872 KB Output is correct
4 Correct 0 ms 6476 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 4 ms 7004 KB Output is correct
7 Correct 8 ms 7400 KB Output is correct
8 Correct 0 ms 7136 KB Output is correct
9 Correct 4 ms 7268 KB Output is correct
10 Correct 7 ms 7400 KB Output is correct
11 Correct 2 ms 6344 KB Output is correct
12 Correct 0 ms 7136 KB Output is correct
13 Correct 5 ms 6740 KB Output is correct
14 Correct 10 ms 6872 KB Output is correct
15 Correct 5 ms 6476 KB Output is correct
16 Correct 2 ms 6476 KB Output is correct
17 Correct 0 ms 6608 KB Output is correct
18 Correct 4 ms 6872 KB Output is correct
19 Correct 3 ms 7136 KB Output is correct
20 Correct 5 ms 7136 KB Output is correct
21 Correct 12 ms 6740 KB Output is correct
22 Correct 0 ms 6344 KB Output is correct
23 Correct 2 ms 6344 KB Output is correct
24 Correct 3 ms 6872 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 8852 KB Output is correct
2 Correct 583 ms 10964 KB Output is correct
3 Correct 1013 ms 7532 KB Output is correct
4 Correct 1019 ms 10040 KB Output is correct
5 Correct 744 ms 54524 KB Output is correct
6 Correct 829 ms 76436 KB Output is correct
7 Correct 837 ms 60596 KB Output is correct
8 Correct 975 ms 102836 KB Output is correct
9 Correct 1787 ms 158936 KB Output is correct
10 Correct 1579 ms 158936 KB Output is correct
11 Correct 1655 ms 159200 KB Output is correct
12 Execution timed out 3000 ms 59144 KB Program timed out