oj.uz

Submission #115498

# Submission time Handle Problem Language Result Execution time Memory
115498 2019-06-07T23:25:30 Z thebes Sails (IOI07_sails) C++14
100 / 100
 266 ms 8764 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 19 ms 6528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2304 KB Output is correct
2 Correct 41 ms 1280 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2724 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 4208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 7748 KB Output is correct
2 Correct 209 ms 8764 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 8056 KB Output is correct
2 Correct 87 ms 8056 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 8152 KB Output is correct
2 Correct 146 ms 4856 KB Output is correct