oj.uz

Submission #15573

# Submission time Handle Problem Language Result Execution time Memory
15573 2015-07-13T00:06:36 Z ainta 통로 위의 개미 (kriii3_X) C++
85 / 85
 2684 ms 87128 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{
    int b, e, ck;
    bool operator<(const Query &p)const{
        return b<p.b;
    }
}w[5], tw[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){
    int s = 0, tc = 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);
    sort(w,w+cnt);
    for(int i=0;i<cnt;i++){
        if(i==0 || w[i].b != w[i-1].e+1)tw[tc].b = w[i].b;
        if(i==cnt-1 || w[i].e+1!=w[i+1].b)tw[tc++].e=w[i].e;
    }
    s=0;
    for(int i=0;i<tc;i++){
        s += Gap(Root,0,2*L-1,tw[i].b,tw[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 0 ms 5552 KB Output is correct
2 Correct 0 ms 5156 KB Output is correct
3 Correct 3 ms 5420 KB Output is correct
4 Correct 2 ms 5288 KB Output is correct
5 Correct 4 ms 5420 KB Output is correct
6 Correct 2 ms 5420 KB Output is correct
7 Correct 5 ms 5684 KB Output is correct
8 Correct 4 ms 5552 KB Output is correct
9 Correct 6 ms 5684 KB Output is correct
10 Correct 4 ms 5684 KB Output is correct
11 Correct 3 ms 5156 KB Output is correct
12 Correct 5 ms 5552 KB Output is correct
13 Correct 6 ms 5288 KB Output is correct
14 Correct 7 ms 5420 KB Output is correct
15 Correct 4 ms 5156 KB Output is correct
16 Correct 0 ms 5288 KB Output is correct
17 Correct 3 ms 5288 KB Output is correct
18 Correct 3 ms 5420 KB Output is correct
19 Correct 3 ms 5552 KB Output is correct
20 Correct 2 ms 5552 KB Output is correct
21 Correct 9 ms 5288 KB Output is correct
22 Correct 3 ms 5156 KB Output is correct
23 Correct 3 ms 5156 KB Output is correct
24 Correct 3 ms 5420 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 6872 KB Output is correct
2 Correct 375 ms 8984 KB Output is correct
3 Correct 723 ms 6344 KB Output is correct
4 Correct 670 ms 8720 KB Output is correct
5 Correct 517 ms 32612 KB Output is correct
6 Correct 562 ms 43568 KB Output is correct
7 Correct 553 ms 35648 KB Output is correct
8 Correct 635 ms 56768 KB Output is correct
9 Correct 1173 ms 86996 KB Output is correct
10 Correct 1092 ms 86996 KB Output is correct
11 Correct 1136 ms 87128 KB Output is correct
12 Correct 2684 ms 35384 KB Output is correct