oj.uz

답안 #65134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65134 2018-08-06T17:10:14 Z edisonhello Sails (IOI07_sails) C++11
100 / 100
 394 ms 13984 KB 
#include<bits/stdc++.h>
using namespace std;

pair<int,int> fan[100005];
int n;
int cnt[100005];
long long ans=0;

struct node{
    node *l,*r;
    int sz,pri;
    long long tag,val,tot;
    int lz(){ return l?l->sz:0; }
    int rz(){ return r?r->sz:0; }
    void addtag(int d){ tag+=d; val+=d; tot+=1ll*d*sz; }
    void push(){ if(l)l->addtag(tag); if(r)r->addtag(tag); tag=0; }
    void pull(){ sz=lz()+rz()+1; tot=val+(l?l->tot:0ll)+(r?r->tot:0ll); }
    node(long long val=0):l(0),r(0),sz(1),pri(rand()),tag(0),val(val),tot(val){}
} *root;

node *merge(node *a,node *b){
    if(!a)return b; if(!b)return a;
    a->push(); b->push();
    if(a->pri>b->pri){
        a->r=merge(a->r,b);
        a->pull();
        return a;
    }
    else{
        b->l=merge(a,b->l);
        b->pull();
        return b;
    }
}
void split_sz(node *s,int sz,node *&a,node *&b){
    if(!s){ a=b=0; return; }
    s->push();
    if(s->lz()>=sz){
        b=s;
        split_sz(s->l,sz,a,b->l);
        b->pull();
    }
    else{
        a=s;
        split_sz(s->r,sz-1-s->lz(),a->r,b);
        a->pull();
    }
}
void split_val(node *s,int val,node *&a,node *&b){
    if(!s){ a=b=0; return; }
    s->push();
    if(s->val<=val){
        a=s;
        split_val(s->r,val,a->r,b);
        a->pull();
    }
    else{
        b=s;
        split_val(s->l,val,a,b->l);
        b->pull();
    }
}

int getR(node *now){
    now->push();
    if(!now->r)return now->val;
    else return getR(now->r);
}
int getL(node *now){
    now->push();
    if(!now->l)return now->val;
    else return getL(now->l);
}

void print(node *now){
    if(!now)return;
    now->push();
    if(now->l)cout<<"(",print(now->l),cout<<")";
    cout<<now->val;
    if(now->r)cout<<"(",print(now->r),cout<<")";
}

int main(){
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    // n=10;
    for(int i=0;i<n;++i){
        cin>>fan[i].first>>fan[i].second;
        // fan[i].first=rand()%20+1;
        // fan[i].second=rand()%(fan[i].first+1);
    }
    sort(fan,fan+n);
    int slots_open=0;
    for(int i=0;i<n;++i){
        while(slots_open<fan[i].first)root=merge(new node(0),root),++slots_open;
        if(fan[i].second==0)continue;
        // cout<<fan[i].first<<" "<<fan[i].second<<endl;
        node *a,*b;
        split_sz(root,fan[i].second,a,b);
        ans+=a->tot;
        a->addtag(1);
        if(a && b){
            int rrr=getR(a);
            int lll=getL(b);
            // cout<<"rrr lll "<<rrr<<" "<<lll<<endl;
            if(rrr>lll){
                node *c,*d,*e,*f;
                split_val(a,rrr-1,c,d);
                split_val(b,lll,e,f);
                a=merge(c,e);
                b=merge(d,f);
            }
        }
        // print(a); cout<<" , "; print(b); cout<<endl;
        root=merge(a,b);
        // print(root); cout<<endl;
    }
    cout<<ans<<endl;
}

Compilation message

sails.cpp: In function 'node* merge(node*, node*)':
sails.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
sails.cpp:22:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(!a)return b; if(!b)return a;
                     ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

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