Submission #899768

#	Time	Username	Problem	Language	Result	Execution time	Memory
899768		sverma22	Sails (IOI07_sails)	C++17	0 / 100	13 ms	3052 KiB

sails

#include <bits/stdc++.h>
using namespace std; 
 
#define int int64_t
 
const int MAXN = 1e5 + 5; 
 
int n; 
int seg[4 * MAXN]; 
 
// highkey this is all useless let's j not call it
void build(int node = 1, int l = 1, int r = MAXN) {
    if(l == r) {
        seg[node] = 0; // normally you do a[l] or whatever not rlly necessary
        return; 
    }
    int mid = (l + r) / 2; 
    build(2 * node, l, mid); 
    build(2 * node + 1, mid + 1, r); 
    seg[node] = seg[2 * node] + seg[2 * node + 1]; 
}
 
// point update alr bet getting a lil used to this segtree shit 
void upd(int x, int val, int node = 1, int l = 1, int r = MAXN) {
    if(l == r) { // should be when l == r == x 
        seg[node] += val; 
        return; 
    }
    int mid = (l + r) / 2; 
    if(x > mid) upd(x, val, 2 * node + 1, mid + 1, r); 
    else upd(x, val, 2 * node, l, mid);
    seg[node] = seg[2 * node] + seg[2 * node + 1]; 
}
 
// i love hte library 
// query will j give the prefix sum
// same as query of [l, r] 1 - x [l, r]
int query(int x, int node = 1, int l = 1, int r = MAXN) {
    // case 1 completely outside 
    if(x < l || r < 1) {
        return 0; 
    }
    // case 2 completely inside 
    if(1 <= l && r <= x) {
        return seg[node]; 
    }
    // case 3 recurse 
    int mid = (l + r) / 2; 
    int lr = query(x, 2 * node, l, mid); 
    int rr = query(x, 2 * node + 1, mid + 1, r); 
    return lr + rr; 
}
 
// shit should be right 
int numGreaterThan(int x, int bound) { // 2 [3, 3]
    // a special case for fucking 0 then 
    if(query(1) <= x) return 0; // yes i have an extra case too 
    int l = 1, r = bound; 
    while(l < r) {
        int mid = (l + r + 1) / 2; // [3, 1] 2 -> answer should be 1 [3, 3] -> should should be 2 
        int res = query(mid); // 3 then u get fucking stuck 
        if(res <= x) {
            r = mid - 1; // we don't even like mid [garunteed progress]
        } else { 
            l = mid; 
        }
    }
    return l; 
}
 
void solve() {
    cin >> n; 
    vector<pair<int, int> > sails(n); 
    for(int i = 0; i < n; i++) cin >> sails[i].first >> sails[i].second; 
 
    cout << 10 << '\n';
    return;
 
    sort(sails.begin(), sails.end()); 
    // ah no need for lazy prop if it's done difference array style and then j doing range queries
 
    for(auto &[height, num] : sails) {
        int val = query(height - num + 1); 
        int r = numGreaterThan(val - 1, height); 
        int l = numGreaterThan(val, height); // 3 3 2 1 0 
        // embarasing i can't implement a binary search that clearnly 
        int numSameToUpd = r - height + num; 
 
        upd(l + 1, 1); 
        upd(l + numSameToUpd + 1, -1); 
        if(r + 1 <= height) {
            upd(r + 1, 1); 
            upd(height + 1, -1); 
        }
 
        // for(int i = 1; i <= height; i++) {
        //     int res = query(i); 
        //     cout << res << ' '; 
        // }
        // cout << '\n';
    }
 
    // that's it though 
    int ans = 0; 
    for(int i = 1; i <= sails[n - 1].first; i++) {
        int res = query(i); 
        ans += (res * (res - 1)) / 2; 
    }
 
    cout << ans << '\n'; 
 
 
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1; // cin >> t; 
    while(t--) {
        solve(); 
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10