oj.uz

Submission #476005

# Submission time Handle Problem Language Result Execution time Memory
476005 2021-09-24T15:05:47 Z cpp219 Sails (IOI07_sails) C++14
100 / 100
 235 ms 11156 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
typedef pair<ld,ll> LD;
const ll N = 1e5 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;

LL a[N];
ll n,ans,sz = 1e5;

struct Node{
    ll mx,mn,sum,lazy;
}st[4*N];
Node spare = {0,0,0};

Node operator + (Node a,Node b){
    Node c;
    c.mn = min(a.mn,b.mn); c.sum = a.sum + b.sum;
    c.lazy = 0; c.mx = max(a.mx,b.mx);
    return c;
}

void Pass(ll id,ll l,ll r){
    ll t = st[id].lazy,mid = (l + r)/2; st[id].lazy = 0;
    st[id*2].mn += t; st[id*2 + 1].mn += t;
    st[id*2].mx += t; st[id*2 + 1].mx += t;
    st[id*2].lazy += t; st[id*2 + 1].lazy += t;
    st[id*2].sum += t*(mid - l + 1);
    st[id*2 + 1].sum += t*(r - mid);
}

void upd(ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        st[id].mn += val; st[id].sum += val*(r - l +1);
        st[id].lazy += val; st[id].mx += val;
        return;
    }
    ll mid = (l + r)/2; Pass(id,l,r);
    upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
    st[id] = st[id*2] + st[id*2 + 1];
}

ll Get(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return 0;
    if (u <= l&&r <= v) return st[id].sum;
    ll mid = (l + r)/2; Pass(id,l,r);
    return Get(id*2,l,mid,u,v) + Get(id*2 + 1,mid + 1,r,u,v);
}

ll WalkFirst(ll id,ll l,ll r,ll val){
    if (l == r) return l;
    ll mid = (l + r)/2; Pass(id,l,r);
    if (st[id*2].mn <= val) return WalkFirst(id*2,l,mid,val);
    return WalkFirst(id*2 + 1,mid + 1,r,val);
}

ll WalkLast(ll id,ll l,ll r,ll val){
    if (l == r) return l;
    ll mid = (l + r)/2; Pass(id,l,r);
    if (st[id*2 + 1].mx >= val) return WalkLast(id*2 + 1,mid + 1,r,val);
    return WalkLast(id*2,l,mid,val);
}

void out(){
    for (ll i = 1;i <= n;i++) cout<<Get(1,1,sz,i,i)<<" ";
    cout<<"\n";
    //exit(0);
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc;
    sort(a + 1,a + n + 1);
    for (ll i = 1;i <= n;i++){
        ll last = a[i].fs - a[i].sc + 1; ans += Get(1,1,sz,last,a[i].fs);
        ll big = Get(1,1,sz,last,last);
        ll st = WalkFirst(1,1,sz,big),en = WalkLast(1,1,sz,big); en = min(en,a[i].fs);
        //cout<<st<<" "<<en<<" "<<big<<"\n";
        upd(1,1,sz,en + 1,a[i].fs,1);
        upd(1,1,sz,st,st + en - last,1); //out();
    }
    cout<<ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 6 ms 7884 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3004 KB Output is correct
2 Correct 61 ms 1344 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3516 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5700 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 10460 KB Output is correct
2 Correct 147 ms 10640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 10876 KB Output is correct
2 Correct 110 ms 9668 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 11156 KB Output is correct
2 Correct 157 ms 5440 KB Output is correct