Submission #1222747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222747		mariamtsagareli	trapezoid (balkan11_trapezoid)	C++20	Compilation error	0 ms	0 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
using i = int;
const i MOD = 30013;

struct Trap { i a,b,c,d; };

struct Node { i mx,cnt; };

struct Seg {
    i mx,cnt;
    Seg(i m=0,i c=0):mx(m),cnt(c){}
};

Seg mergeSeg(const Seg &x,const Seg &y){
    if(x.mx>y.mx) return x;
    if(y.mx>x.mx) return y;
    if(x.mx==0) return Seg(0,1);
    return Seg(x.mx,(x.cnt+y.cnt)%MOD);
}

struct ST{ i n; vector<Seg> t;
    ST(i m):n(m),t(4*m+4,Seg(0,1)){}
    Seg q(i p,i l,i r,i ql,i qr){
        if(r<ql||l>qr) return Seg(0,1);
        if(ql<=l&&r<=qr) return t[p];
        i m=(l+r)>>1;
        return mergeSeg(q(p<<1,l,m,ql,qr),q(p<<1|1,m+1,r,ql,qr));
    }
    Seg q(i l,i r){ return l>r?Seg(0,1):q(1,1,n,l,r); }
    void u(i p,i l,i r,i pos,Seg v){
        if(l==r){ t[p]=mergeSeg(t[p],v); return; }
        i m=(l+r)>>1;
        if(pos<=m) u(p<<1,l,m,pos,v); else u(p<<1|1,m+1,r,pos,v);
        t[p]=mergeSeg(t[p<<1],t[p<<1|1]);
    }
    void u(i pos,Seg v){ u(1,1,n,pos,v); }
};

struct BIT{ i n; vector<i> f;
    BIT(i m):n(m),f(m+1,0){}
    void add(i i,i v){ for(;i<=n;i+=i&-i) f[i]=(f[i]+v)%MOD; }
    i sum(i i){ i s=0; for(;i>0;i-=i&-i) s=(s+f[i])%MOD; return s; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    i N; cin>>N;
    vector<Trap> A(N);
    vector<i> C; C.reserve(4*N);
    for(i i=0;i<N;i++){ cin>>A[i].a>>A[i].b>>A[i].c>>A[i].d; C.insert(C.end(),{A[i].a,A[i].b,A[i].c,A[i].d}); }
    sort(C.begin(),C.end()); C.erase(unique(C.begin(),C.end()),C.end());
    auto id=[&](i v){ return int(lower_bound(C.begin(),C.end(),v)-C.begin()+1); };
    i M=C.size();
    for(auto &t:A){ t.a=id(t.a); t.b=id(t.b); t.c=id(t.c); t.d=id(t.d); }
    sort(A.begin(),A.end(),[](auto &x,auto &y){ return x.a!=y.a?x.a<y.a:x.b<y.b; });
    ST st1(M),st2(M);
    vector<Node> dp(N);
    for(i i=0;i<N;i++){
        auto s1=st1.q(1,A[i].a-1);
        auto s2=st2.q(1,A[i].c-1);
        auto s=mergeSeg(s1,s2);
        dp[i].mx=s.mx+1; dp[i].cnt=s.cnt;
        st1.u(A[i].b,Seg(dp[i].mx,dp[i].cnt));
        st2.u(A[i].d,Seg(dp[i].mx,dp[i].cnt));
    }
    i K=0; for(auto &x:dp) K=max(K,x.mx);
    vector<vector<i>> by(K+1);
    for(i i=0;i<N;i++) by[dp[i].mx].push_back(i);
    vector<i> cnt2(N);
    for(i k=1;k<K;k++){
        BIT bit(M);
        for(i idx:by[k]) bit.add(A[idx].d,dp[idx].cnt);
        for(i idx:by[k+1]) cnt2[idx]=bit.sum(A[idx].c-1);
        for(i idx:by[k+1]) dp[idx].cnt=cnt2[idx];
    }
    i total=0;
    for(i idx:by[K]) total=(total+dp[idx].cnt)%MOD;
    cout<<K<<" "<<total;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp:42:18: error: 'i' is not a type
   42 |     void add(i i,i v){ for(;i<=n;i+=i&-i) f[i]=(f[i]+v)%MOD; }
      |                  ^
trapezoid.cpp: In member function 'i BIT::sum(i)':
trapezoid.cpp:43:19: error: expected ';' before 's'
   43 |     i sum(i i){ i s=0; for(;i>0;i-=i&-i) s=(s+f[i])%MOD; return s; }
      |                   ^
trapezoid.cpp:43:42: error: 's' was not declared in this scope
   43 |     i sum(i i){ i s=0; for(;i>0;i-=i&-i) s=(s+f[i])%MOD; return s; }
      |                                          ^
trapezoid.cpp:43:65: error: 's' was not declared in this scope
   43 |     i sum(i i){ i s=0; for(;i>0;i-=i&-i) s=(s+f[i])%MOD; return s; }
      |                                                                 ^