oj.uz

Submission #959507

# Submission time Handle Problem Language Result Execution time Memory
959507 2024-04-08T10:45:17 Z Hugo1729 Sails (IOI07_sails) C++11
0 / 100
 41 ms 35420 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second

int sz=1,n;
vector<ll> t1, lazy1, t2, lazy2;
ll ans=0;

void push1(int v){
    t1[v*2]+=lazy1[v];
    lazy1[v*2]+=lazy1[v];
    t1[v*2+1]+=lazy1[v];
    lazy1[v*2+1]+=lazy1[v];
    lazy1[v]=0;
}

void push2(int v,int width){
    width>>=1;
    t2[v*2]+=lazy2[v]*width;
    lazy2[v*2]+=lazy2[v];
    t2[v*2+1]+=lazy2[v]*width;
    lazy2[v*2+1]+=lazy2[v];
    lazy2[v]=0;
}

void update1(int v, int tl, int tr, int l, int r, int val){
    if(l>r)return;
    if(tl==l&&tr==r){
        t1[v]+=val;
        lazy1[v]+=val;
        return;
    }
    push1(v);
    int mid=(tl+tr)/2;
    update1(2*v,tl,mid,l,min(mid,r),val);
    update1(2*v+1,mid+1,tr,max(mid+1,l),r,val);
    t1[v]=min(t1[v*2],t1[v*2+1]);
}

void update2(int v, int tl, int tr, int l, int r, int val){
    if(l>r)return;
    if(tl==l&&tr==r){
        t2[v]+=val*(tr-tl+1);
        lazy2[v]+=val;
        return;
    }
    push2(v,tr-tl+1);
    int mid=(tl+tr)/2;
    update2(2*v,tl,mid,l,min(mid,r),val);
    update2(2*v+1,mid+1,tr,max(mid+1,l),r,val);
    t2[v]=t2[v*2]+t2[v*2+1];
}

void update(int v, int tl, int tr, int l, int r, int val){
    update1(v, tl, tr, l, r, val);
    update2(v, tl, tr, l, r, val);
}
    

ll query2(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l&&tr==r){
        return t2[v];
    }
    push2(v,tr-tl+1);
    int mid=(tl+tr)/2;
    return query2(2*v,tl,mid,l,min(mid,r))+
    query2(2*v+1,mid+1,tr,max(mid+1,l),r);
}

int find1(int k){
    int v=1;

    while(v<sz){
        push1(v);
        if(t1[v*2]<=k)v<<=1;
        else v=v*2+1;
    }

    return v-sz+1;
}

void pushall2(int v, int tl, int tr){
    if(tr>tl){
        // cout << v << ' ' << tr-tl+1 << '\n';
        push2(v,tr-tl+1);
        int mid=(tl+tr)/2;
        pushall2(v*2,tl,mid);
        pushall2(2*v+1,mid+1,tr);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    vector<pair<int,int>> flags(n);
    for(int i=0;i<n;i++){
        cin >> flags[i].f >> flags[i].s;
    }

    sort(flags.begin(),flags.end());

    while(sz<flags[n-1].f+1)sz<<=1;
    sz<<=1;

    t1.assign(2*sz+5,1000001);
    lazy1.assign(2*sz+5,0);

    t2.assign(2*sz+5,0);
    lazy2.assign(2*sz+5,0);

    int sus=1;

    for(int i=0;i<n;i++){
        int h=flags[i].f,k=flags[i].s;

        update1(1,1,sz,sus,h,-1000001);
        sus=h+1;

        int index=find1(t1[sz+h-k]);
        int next = min(find1(t1[sz+h-k]-1),h+1);

        // cout << h << ' ' << k << ' ' << index << ' ' << next << '\n';

        ans+=query2(1,1,sz,h-k+1,h);

        update(1,1,sz,index,h,1);
        update(1,1,sz,next-1-(h-k+1)+index+1,next-1,-1);
        // update(1,1,sz,1,k,1);

        // index=find();
        // cout << 'b' <<(k)*(t[index+sz-1]) <<' ' << index << '\n';
        // ans+=(k)*(t[index+sz-1]);
        // update(1,1,sz,index,index+k-1,1);
        // for(int i=1;i<sz;i++)push1(i);
        // pushall2(1,1,sz);
        // for(int i=1;i<sz*2;i++)cout << t1[i] << ' ';
        // cout << '\n';
        // for(int i=1;i<sz*2;i++)cout << t2[i] << ' ';
        // cout << '\n';
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 18012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 35100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 35316 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 35420 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -