oj.uz

Submission #254366

# Submission time Handle Problem Language Result Execution time Memory
254366 2020-07-29T21:54:30 Z fivefourthreeone Sails (IOI07_sails) C++17
100 / 100
 173 ms 3192 KB 
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> mp;*/
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = -1e6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100005;
ttgl arr[mxN];
int seg[4*mxN];
int segmax[4*mxN];
int del[4*mxN];
int n;
void push(int i) {
    del[2*i]+=del[i];
    del[2*i+1]+=del[i];
    del[i] = 0;
}
void resolve(int i) {
    seg[i] = min(seg[2*i] + del[2*i], seg[2*i+1] + del[2*i+1]);
    segmax[i] = max(segmax[2*i] + del[2*i], segmax[2*i+1] + del[2*i+1]);
}
void upd(int l, int r, int ch, int i=1, int le = 0, int rr = mxN-1) {
    if(l>r)return;
    if(le>r||rr<l) return;
    if(le>=l&&rr<=r) {
        del[i]+=ch;
        return;
    }
    int mid = (le+rr)/2;
    push(i);
    upd(l, r, ch, 2*i, le, mid);
    upd(l, r, ch, 2*i+1, mid+1, rr);
    resolve(i);
    return;
}
int getnum(int pos, int i=1, int le=0, int rr=mxN-1) {
    if(le>pos||rr<pos)return INF;
    if(le==rr&&le==pos) {
        return seg[i]+del[i];
    }
    push(i);
    resolve(i);
    int mid = (le+rr)/2;
    return min(getnum(pos, 2*i, le, mid), getnum(pos, 2*i+1, mid+1, rr));
}
int query(int val, int i=1, int le = 0, int rr=mxN-1) {
    //cout<<val<<" "<<le<<" "<<rr<<" "<<(seg[i]+del[i])<<endl;
    if(i==1&&val>segmax[i]+del[i]) {
        return 0;
    }
    if(le==rr) {
        if(val>segmax[i]+del[i]) return le;
        else return mxN;
    }
    push(i);
    resolve(i);
    int mid = (le+rr)/2;
    if(val>seg[2*i] + del[2*i]) {
        return query(val, 2*i, le, mid);
    }else {
        return query(val, 2*i+1, mid+1, rr);
    }
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    owo(i, 0, n) {
        cin>>arr[i].first>>arr[i].second;
        arr[i].first--;
    }
    sort(arr, arr+n);
    //query(0);
    owo(i, 0, n) {
        int start = arr[i].first-arr[i].second+1;
        int smal = getnum(start);
        int r = min(query(smal)-1, arr[i].first);
        int l = query(smal+1);
        //cout<<arr[i].first<<" "<<arr[i].second<<" "<<smal<<" "<<l<<" "<<r<<" "<<start<<"\n";
        upd(l, l+r-start, 1);
        upd(r+1, arr[i].first, 1);
        //cout<<"----------------------\n";
        //owo(i, 0, 6) {
            //cout<<getnum(i)<<" ";
        //}
        //cout<<"\n";
        //query(0);
    }
    ll ans =0;
    owo(i, 0, mxN) {
        int val = getnum(i);
        ans+=1LL*val*(val-1)/2;
    }
    cout<<ans<<"\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2432 KB Output is correct
2 Correct 20 ms 2432 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2432 KB Output is correct
2 Correct 18 ms 2432 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2428 KB Output is correct
2 Correct 19 ms 2432 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2424 KB Output is correct
2 Correct 23 ms 2396 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2432 KB Output is correct
2 Correct 21 ms 2432 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2452 KB Output is correct
2 Correct 56 ms 2680 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2680 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 2808 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2936 KB Output is correct
2 Correct 134 ms 2940 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 3064 KB Output is correct
2 Correct 100 ms 3100 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 3172 KB Output is correct
2 Correct 129 ms 3192 KB Output is correct