oj.uz

Submission #15543

# Submission time Handle Problem Language Result Execution time Memory
15543 2015-07-12T09:23:30 Z ainta 통로 위의 개미 (kriii3_X) C++
30 / 85
 3000 ms 160376 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][1010], 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] == 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 4 ms 8444 KB Output is correct
2 Correct 3 ms 7520 KB Output is correct
3 Correct 4 ms 8048 KB Output is correct
4 Correct 4 ms 7652 KB Output is correct
5 Correct 2 ms 8180 KB Output is correct
6 Correct 5 ms 8180 KB Output is correct
7 Correct 4 ms 8576 KB Output is correct
8 Correct 6 ms 8312 KB Output is correct
9 Correct 7 ms 8444 KB Output is correct
10 Correct 4 ms 8576 KB Output is correct
11 Correct 4 ms 7520 KB Output is correct
12 Correct 5 ms 8312 KB Output is correct
13 Correct 8 ms 7916 KB Output is correct
14 Correct 10 ms 8048 KB Output is correct
15 Correct 2 ms 7652 KB Output is correct
16 Correct 3 ms 7652 KB Output is correct
17 Correct 0 ms 7784 KB Output is correct
18 Correct 3 ms 8048 KB Output is correct
19 Correct 4 ms 8312 KB Output is correct
20 Correct 5 ms 8312 KB Output is correct
21 Correct 13 ms 7916 KB Output is correct
22 Correct 2 ms 7520 KB Output is correct
23 Correct 0 ms 7520 KB Output is correct
24 Correct 0 ms 8048 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 10028 KB Output is correct
2 Correct 601 ms 12140 KB Output is correct
3 Correct 1030 ms 8708 KB Output is correct
4 Correct 1026 ms 11216 KB Output is correct
5 Correct 764 ms 55700 KB Output is correct
6 Correct 782 ms 77612 KB Output is correct
7 Correct 872 ms 61772 KB Output is correct
8 Correct 976 ms 104012 KB Output is correct
9 Correct 1817 ms 160112 KB Output is correct
10 Correct 1624 ms 160112 KB Output is correct
11 Correct 1667 ms 160376 KB Output is correct
12 Execution timed out 3000 ms 59792 KB Program timed out