oj.uz

답안 #115496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115496 2019-06-07T23:09:43 Z thebes Sails (IOI07_sails) C++14
50 / 100
 1000 ms 7816 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);
}
void unite(nd *&n,nd *l,nd *r){
    if(!l||!r){n=l?l:r;return;}
    if(l->p<r->p) swap(l,r);
    nd *lt, *rt; upd_lz(l); upd_lz(r);
    spl(r, lt, rt, l->k);
    unite(l->l,l->l,lt);
    unite(l->r,l->r,rt);
    n=l; upd(n);
}

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

signed main(){
    rt = NULL; srand(time(0));
    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++;
        unite(rt, l, r);
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:67: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:68: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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 700 KB Output is correct
2 Correct 310 ms 7056 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 2240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 2680 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 1924 KB Time limit exceeded

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1078 ms 7816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1078 ms 3576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 3216 KB Time limit exceeded
2 Halted 0 ms 0 KB -