oj.uz

Submission #1068487

# Submission time Handle Problem Language Result Execution time Memory
1068487 2024-08-21T10:11:17 Z beaconmc Sails (IOI07_sails) C++14
100 / 100
 534 ms 9984 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
const ll maxn = 100005;

ll tree[maxn*4];
ll lazy[maxn*4];

ll calc(ll k, ll x, ll y){
    return tree[k] + lazy[k] * (y-x+1);
}

void push(ll k, ll x, ll y){
    lazy[k*2] += lazy[k];
    lazy[k*2+1] += lazy[k];
    tree[k] += lazy[k] * (y-x+1);
    lazy[k] = 0;
}

void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y = maxn-1){
    if (y<a || x>b) return;
    if (a<=x && y<=b){
        lazy[k] += val;
        return;
    }
    push(k,x,y);
    ll mid  = (x+y)/2;
    update(a, b, val, k*2, x, mid);
    update(a, b, val, k*2+1, mid+1, y);

    tree[k] = calc(k*2, x, mid) + calc(k*2+1, mid+1, y);
}

ll query(ll a, ll b, ll k=1, ll x=0, ll y=maxn-1){
    if (y<a || x>b) return 0;
    if (a<=x && y<=b){
        return calc(k,x,y);
    }
    push(k,x,y);
    ll mid  = (x+y)/2;
    return query(a,b,k*2,x,mid) + query(a,b,k*2+1,mid+1,y);
}

int main(){
    ll n;
    cin >> n;
    vector<vector<ll>> stuff;
    FOR(i,0,n){
        ll h,k;
        cin >> h >> k;
        stuff.push_back({h,k});
    }

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

    for (auto&i : stuff){

        ll num = i[1];
        num--;
        ll pos = maxn-i[0];


        ll val = query(pos+num, pos+num);

        ll lo = pos, hi = maxn-1;
        while (lo < hi){

            ll mid = (lo+hi+1)/2;


            ll temp = query(mid, mid);

            if (temp <= val) lo = mid;
            else hi = mid-1;
        }
        ll lasts = lo;

        lo = pos, hi = maxn-1;

        while (lo < hi){

            ll mid = (lo+hi)/2;

            ll temp = query(mid, mid);
            if (temp >= val) hi = mid;
            else lo = mid+1;
        }
        ll firsts = lo;


        update(pos, firsts-1, 1);


        ll overlap = pos+num - firsts;
        update(lasts-overlap, lasts, 1);


    }
    ll ans = 0;
    FOR(i,0,maxn){
        ll temp = query(i,i);

        ans += (temp * (temp-1))/2;

    }
    cout << ans << endl;


}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4444 KB Output is correct
2 Correct 13 ms 3416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3308 KB Output is correct
2 Correct 12 ms 4444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3420 KB Output is correct
2 Correct 12 ms 3428 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3420 KB Output is correct
2 Correct 14 ms 3420 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3668 KB Output is correct
2 Correct 104 ms 5384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6156 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 6148 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 7932 KB Output is correct
2 Correct 391 ms 9720 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 9468 KB Output is correct
2 Correct 343 ms 9984 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 8956 KB Output is correct
2 Correct 353 ms 9060 KB Output is correct