oj.uz

Submission #15541

# Submission time Handle Problem Language Result Execution time Memory
15541 2015-07-12T09:20:57 Z ainta 통로 위의 개미 (kriii3_X) C++
30 / 85
 3000 ms 158008 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[501][1010], In[201000], SZ[601], MM, TP[201000];
short 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] == 400)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] == 1000){
        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 7 ms 6076 KB Output is correct
2 Correct 4 ms 5152 KB Output is correct
3 Correct 3 ms 5680 KB Output is correct
4 Correct 4 ms 5284 KB Output is correct
5 Correct 5 ms 5812 KB Output is correct
6 Correct 5 ms 5812 KB Output is correct
7 Correct 6 ms 6208 KB Output is correct
8 Correct 4 ms 5944 KB Output is correct
9 Correct 5 ms 6076 KB Output is correct
10 Correct 7 ms 6208 KB Output is correct
11 Correct 5 ms 5152 KB Output is correct
12 Correct 4 ms 5944 KB Output is correct
13 Correct 5 ms 5548 KB Output is correct
14 Correct 9 ms 5680 KB Output is correct
15 Correct 4 ms 5284 KB Output is correct
16 Correct 3 ms 5284 KB Output is correct
17 Correct 2 ms 5416 KB Output is correct
18 Correct 0 ms 5680 KB Output is correct
19 Correct 0 ms 5944 KB Output is correct
20 Correct 3 ms 5944 KB Output is correct
21 Correct 13 ms 5548 KB Output is correct
22 Correct 2 ms 5152 KB Output is correct
23 Correct 4 ms 5152 KB Output is correct
24 Correct 5 ms 5680 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 7660 KB Output is correct
2 Correct 590 ms 9772 KB Output is correct
3 Correct 1023 ms 6340 KB Output is correct
4 Correct 1028 ms 8848 KB Output is correct
5 Correct 808 ms 53332 KB Output is correct
6 Correct 809 ms 75244 KB Output is correct
7 Correct 869 ms 59404 KB Output is correct
8 Correct 967 ms 101644 KB Output is correct
9 Correct 1795 ms 157744 KB Output is correct
10 Correct 1658 ms 157744 KB Output is correct
11 Correct 1592 ms 158008 KB Output is correct
12 Execution timed out 3000 ms 58348 KB Program timed out