oj.uz

Submission #15570

# Submission time Handle Problem Language Result Execution time Memory
15570 2015-07-12T23:59:55 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, int b, int e, int x, int y){
    if(b==e){
        nd->S+=y;
        return;
    }
    int m = b+(e-b)/2;
    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, int b, int e, int s, int l){
    if(b==s&&e==l){
        return nd->S;
    }
    int m = b+(e-b)/2, 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 3 ms 5548 KB Output is correct
2 Correct 4 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 3 ms 5416 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 4 ms 5548 KB Output is correct
9 Correct 6 ms 5680 KB Output is correct
10 Correct 4 ms 5680 KB Output is correct
11 Correct 4 ms 5152 KB Output is correct
12 Correct 0 ms 5548 KB Output is correct
13 Correct 6 ms 5284 KB Output is correct
14 Correct 9 ms 5416 KB Output is correct
15 Correct 5 ms 5152 KB Output is correct
16 Correct 0 ms 5284 KB Output is correct
17 Correct 3 ms 5284 KB Output is correct
18 Correct 3 ms 5416 KB Output is correct
19 Correct 2 ms 5548 KB Output is correct
20 Correct 4 ms 5548 KB Output is correct
21 Correct 11 ms 5284 KB Output is correct
22 Correct 4 ms 5152 KB Output is correct
23 Correct 0 ms 5152 KB Output is correct
24 Correct 2 ms 5416 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 6868 KB Output is correct
2 Correct 491 ms 8980 KB Output is correct
3 Correct 994 ms 6340 KB Output is correct
4 Correct 921 ms 8716 KB Output is correct
5 Correct 602 ms 32608 KB Output is correct
6 Correct 708 ms 43564 KB Output is correct
7 Correct 701 ms 35644 KB Output is correct
8 Correct 789 ms 56764 KB Output is correct
9 Correct 1445 ms 86992 KB Output is correct
10 Correct 1279 ms 86992 KB Output is correct
11 Correct 1432 ms 87124 KB Output is correct
12 Execution timed out 3000 ms 35380 KB Program timed out