oj.uz

Submission #15538

# Submission time Handle Problem Language Result Execution time Memory
15538 2015-07-12T08:59:07 Z ainta 통로 위의 개미 (kriii3_X) C++
Compilation error
 0 ms 0 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, int x, int 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, int s, int 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[501][1010], In[201000], SZ[601], MM, TP[201000];
short P[101000];

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,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);
        }
    }
}

Compilation message

X.cpp: In function ‘int Gap(SegTree*, long long int, long long int, int, int)’:
X.cpp:47:54: error: no matching function for call to ‘min(long long int&, int&)’
     if(nd->c1 && s <= m)r += Gap(nd->c1,b,m,s,min(m,l));
                                                      ^
X.cpp:47:54: note: candidates are:
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from X.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:194:5: note: template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:194:5: note:   template argument deduction/substitution failed:
X.cpp:47:54: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
     if(nd->c1 && s <= m)r += Gap(nd->c1,b,m,s,min(m,l));
                                                      ^
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from X.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:240:5: note: template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:240:5: note:   template argument deduction/substitution failed:
X.cpp:47:54: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
     if(nd->c1 && s <= m)r += Gap(nd->c1,b,m,s,min(m,l));
                                                      ^
X.cpp:48:55: error: no matching function for call to ‘max(long long int, int&)’
     if(nd->c2 && l > m)r += Gap(nd->c2,m+1,e,max(m+1,s),l);
                                                       ^
X.cpp:48:55: note: candidates are:
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from X.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:217:5: note: template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:217:5: note:   template argument deduction/substitution failed:
X.cpp:48:55: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
     if(nd->c2 && l > m)r += Gap(nd->c2,m+1,e,max(m+1,s),l);
                                                       ^
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from X.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:261:5: note: template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:261:5: note:   template argument deduction/substitution failed:
X.cpp:48:55: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
     if(nd->c2 && l > m)r += Gap(nd->c2,m+1,e,max(m+1,s),l);
                                                       ^
X.cpp: In function ‘int main()’:
X.cpp:123:9: warning: unused variable ‘i’ [-Wunused-variable]
     int i, p, r;
         ^
X.cpp:128:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&L,&Q);
                            ^
X.cpp:131:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%d%lld",&t,&p,&a);
                                     ^
X.cpp:134:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
                           ^