oj.uz

Submission #15515

# Submission time Handle Problem Language Result Execution time Memory
15515 2015-07-12T08:45:34 Z ainta 통로 위의 개미 (kriii3_X) C++
30 / 85
 3000 ms 158008 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
struct SegTree{
    SegTree *c1, *c2;
    long long S;
    SegTree(){
        c1=c2=NULL;
        S=0;
    }
};
long long L, Q, cnt;
long long 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;
}

long long 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;
}

long long 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(long long 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;
    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;
    }
    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] == 1000){
        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(){
    long long i, be, ed, mid, r;
    long long t;
    long long p;
    long long a, b;
    scanf("%lld%lld",&L,&Q);
    Root = new SegTree();
    while(Q--){
        scanf("%lld%lld%lld",&t,&p,&a);
        t%=(2*L);
        if(p==1){
            scanf("%lld",&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("%lld\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 0 ms 5152 KB Output is correct
3 Correct 4 ms 5680 KB Output is correct
4 Correct 4 ms 5284 KB Output is correct
5 Correct 3 ms 5812 KB Output is correct
6 Correct 5 ms 5812 KB Output is correct
7 Correct 7 ms 6208 KB Output is correct
8 Correct 0 ms 5944 KB Output is correct
9 Correct 5 ms 6076 KB Output is correct
10 Correct 4 ms 6208 KB Output is correct
11 Correct 0 ms 5152 KB Output is correct
12 Correct 5 ms 5944 KB Output is correct
13 Correct 7 ms 5548 KB Output is correct
14 Correct 6 ms 5680 KB Output is correct
15 Correct 4 ms 5284 KB Output is correct
16 Correct 2 ms 5284 KB Output is correct
17 Correct 0 ms 5416 KB Output is correct
18 Correct 3 ms 5680 KB Output is correct
19 Correct 4 ms 5944 KB Output is correct
20 Correct 3 ms 5944 KB Output is correct
21 Correct 3 ms 5548 KB Output is correct
22 Correct 4 ms 5152 KB Output is correct
23 Correct 3 ms 5152 KB Output is correct
24 Correct 4 ms 5680 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 7660 KB Output is correct
2 Correct 531 ms 9772 KB Output is correct
3 Correct 943 ms 6340 KB Output is correct
4 Correct 886 ms 8848 KB Output is correct
5 Correct 701 ms 53332 KB Output is correct
6 Correct 737 ms 75244 KB Output is correct
7 Correct 772 ms 59404 KB Output is correct
8 Correct 874 ms 101644 KB Output is correct
9 Correct 1626 ms 157744 KB Output is correct
10 Correct 1466 ms 157744 KB Output is correct
11 Correct 1418 ms 158008 KB Output is correct
12 Execution timed out 3000 ms 62044 KB Program timed out