oj.uz

Submission #1068473

# Submission time Handle Problem Language Result Execution time Memory
1068473 2024-08-21T10:04:42 Z beaconmc Sails (IOI07_sails) C++14
60 / 100
 1000 ms 9256 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 = n-i[0];


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

        ll lo = pos, hi = n-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 = n;

        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,n){
        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 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 432 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 2908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2892 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 5388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 8776 KB Output is correct
2 Correct 382 ms 9256 KB Output is correct