Submission #115498

#	Time	Username	Problem	Language	Result	Execution time	Memory
115498		thebes	Sails (IOI07_sails)	C++14	100 / 100	266 ms	8764 KiB

sails

#include <bits/stdc++.h>
using namespace std;

#define int long long
struct nd{
    int k, sm, sz, f, p; nd *l, *r;
    nd(int kk):k(kk),sm(kk),sz(1),f(0),p(rand()),l(0),r(0){}
}*rt;
inline int sz(nd *n){return n?n->sz:0;}
inline void upd_lz(nd *&n);
inline int sm(nd *n){
    if(!n) return 0;
    if(n->f) upd_lz(n);
    return n->sm;
}
inline void prop(nd *&n,int f){
    if(!n) return;
    n->f += f;
}
inline void upd_lz(nd *&n){
    if(!n||!n->f) return;
    n->sm += n->sz*n->f; n->k += n->f;
    prop(n->l,n->f); prop(n->r,n->f);
    n->f = 0;
}
inline void upd(nd *&n){
    if(!n) return;
    n->sz = sz(n->l)+sz(n->r)+1;
    n->sm = sm(n->l)+sm(n->r)+n->k;
}
void split(nd *n,nd *&l,nd *&r,int k){
    upd_lz(n);
    if(!n) l=r=NULL;
    else if(sz(n->l)+1>k) split(n->l,l,n->l,k),r=n;
    else split(n->r,n->r,r,k-sz(n->l)-1),l=n;
    upd(n);
}
void mrg(nd *&n,nd *l,nd *r){
    if(!l||!r) n=l?l:r;
    else if(l->p>r->p) upd_lz(l),mrg(l->r,l->r,r),n=l;
    else upd_lz(r),mrg(r->l,l,r->l),n=r;
    upd(n);
}
void spl(nd *n,nd *&l,nd *&r,int k){
    upd_lz(n);
    if(!n) l=r=NULL;
    else if(n->k<=k) spl(n->r,n->r,r,k),l=n;
    else spl(n->l,l,n->l,k),r=n;
    upd(n);
}
int get_f(nd *n){
    if(!n) return 1<<30;
    upd_lz(n);
    int m = n->k;
    return min(m, get_f(n->l));
}

const int MN = 1e5+5;
int N, i, x, y, ans, lst=1;
pair<int,int> arr[MN];

signed main(){
    rt = NULL; srand(22);
    for(scanf("%lld",&N),i=1;i<=N;i++)
        scanf("%lld%lld",&arr[i].first,&arr[i].second);
    sort(arr+1,arr+N+1,[](pair<int,int>i,pair<int,int>j){return i.first<j.first;});
    for(i=1;i<=N;i++){
        while(lst<=arr[i].first) mrg(rt,new nd(0),rt),lst++;
        nd *l, *r;
        split(rt, l, r, arr[i].second);
        ans += sm(l);
        if(l) l->f++;
        if(r){
            nd *lt, *ls, *rt, *rs;
            int kk = get_f(r);
            spl(l, ls, lt, kk);
            spl(r, rs, rt, kk);
            mrg(l, ls, rs);
            mrg(r, lt, rt);
        }
        mrg(rt, l, r);
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:64:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&N),i=1;i<=N;i++)
         ~~~~~~~~~~~~~~~~^~~~
sails.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&arr[i].first,&arr[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10