oj.uz

Submission #834895

# Submission time Handle Problem Language Result Execution time Memory
834895 2023-08-22T22:57:47 Z Magikarp4000 Sails (IOI07_sails) C++17
100 / 100
 498 ms 7252 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int64_t(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#define int long long

struct Node {
    int x,lz;
};

const int MAXN = 1e5+5;
int n;
vector<PII> v;
Node st[MAXN*4+10];

void pushdown(int s) {
    st[s*2].x += st[s].lz;
    st[s*2].lz += st[s].lz;
    st[s*2+1].x += st[s].lz;
    st[s*2+1].lz += st[s].lz;
    st[s].lz = 0LL;
}

void update(int s, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (l <= tl && r >= tr) {
        st[s].x += val;
        st[s].lz += val;
    }
    else {
        pushdown(s);
        int tm = (tl+tr)/2;
        if (l <= tm) update(s*2,tl,tm,l,r,val);
        if (r > tm) update(s*2+1,tm+1,tr,l,r,val);
        st[s].x = st[s*2].x+st[s*2+1].x;
    }
}

int query(int s, int tl, int tr, int l, int r) {
    if (l <= tl && r >= tr) return st[s].x;
    pushdown(s);
    int tm = (tl+tr)/2;
    int cur = 0LL;
    if (l <= tm) cur += query(s*2,tl,tm,l,r);
    if (r > tm) cur += query(s*2+1,tm+1,tr,l,r);
    return cur;
}

int query(int l, int r) {return query(1,0,MAXN-1,l,r);}
void update(int l, int r, int val) {update(1,0,MAXN-1,l,r,val);}

signed main() {
    OPTM;
    cin >> n;
    FOR(i,0,n) {
        int h,k; cin >> h >> k;
        v.PB({h,k});
    }
    sort(ALL(v));
    FOR(i,0,n) {
        int h = v[i].F-1, k = v[i].S;
        int val = query(h-k+1,h-k+1);
        int l = 0, r = h;
        while (l < r) {
            int mid = (l+r)/2;
            if (query(mid,mid) <= val) r = mid;
            else l = mid+1;
        }
        int sta = query(l,l) == val ? l : l+1;
        l = 0; r = h;
        while (l < r) {
            int mid = (l+r)/2;
            if (query(mid,mid) < val) r = mid;
            else l = mid+1;
        }
        int en = query(l,l) == val ? l : l-1;
        int rem = k-(h-en);
        update(en+1,h,1LL);
        update(sta,sta+rem-1,1LL);
    }
    int res = 0LL;
    FOR(i,0,MAXN-1) {
        int val = query(i,i);
        res += (val*(val-1LL))/2LL;
    }
    cout << res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4356 KB Output is correct
2 Correct 11 ms 4360 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4384 KB Output is correct
2 Correct 11 ms 4332 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4456 KB Output is correct
2 Correct 17 ms 4468 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4736 KB Output is correct
2 Correct 121 ms 5324 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5324 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5772 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 6528 KB Output is correct
2 Correct 329 ms 6568 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 7084 KB Output is correct
2 Correct 285 ms 6568 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 7252 KB Output is correct
2 Correct 330 ms 7108 KB Output is correct