oj.uz

Submission #15563

# Submission time Handle Problem Language Result Execution time Memory
15563 2015-07-12T23:48:20 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, 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(){
    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 0 ms 5284 KB Output is correct
5 Correct 5 ms 5812 KB Output is correct
6 Correct 3 ms 5812 KB Output is correct
7 Correct 4 ms 6208 KB Output is correct
8 Correct 6 ms 5944 KB Output is correct
9 Correct 6 ms 6076 KB Output is correct
10 Correct 6 ms 6208 KB Output is correct
11 Correct 5 ms 5152 KB Output is correct
12 Correct 5 ms 5944 KB Output is correct
13 Correct 3 ms 5548 KB Output is correct
14 Correct 9 ms 5680 KB Output is correct
15 Correct 5 ms 5284 KB Output is correct
16 Correct 0 ms 5284 KB Output is correct
17 Correct 3 ms 5416 KB Output is correct
18 Correct 4 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 11 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 2 ms 5680 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 7660 KB Output is correct
2 Correct 512 ms 9772 KB Output is correct
3 Correct 918 ms 6340 KB Output is correct
4 Correct 861 ms 8848 KB Output is correct
5 Correct 665 ms 53332 KB Output is correct
6 Correct 767 ms 75244 KB Output is correct
7 Correct 741 ms 59404 KB Output is correct
8 Correct 824 ms 101644 KB Output is correct
9 Correct 1600 ms 157744 KB Output is correct
10 Correct 1387 ms 157744 KB Output is correct
11 Correct 1504 ms 158008 KB Output is correct
12 Execution timed out 3000 ms 62044 KB Program timed out