Submission #950330

#	Time	Username	Problem	Language	Result	Execution time	Memory
950330		Esgeer	Sails (IOI07_sails)	C++17	25 / 100	129 ms	8428 KiB

sails

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <unistd.h>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp << " " <<
#define F(i, s, n) for(int i = s; i < n; i++)
#define pb push_back
#define fi first
#define se second

int mod = 1e9+7;
int inf = 1e16;
const int N = 2e5+5;

int t[4*N];
int lazy[4*N];

void push(int node, int l, int r) {
    if(lazy[node] == 0) return;
    t[node] += lazy[node];
    if(l != r) {
        lazy[node*2+1] += lazy[node];
        lazy[node*2+2] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int L, int R) {
    push(node, l, r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lazy[node]++;
        push(node, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(node*2+1, l, mid, L, R);
    update(node*2+2, mid+1, r, L, R);
    t[node] = min(t[node*2+1], t[node*2+2]);
}
int lb(int node, int l, int r, int val) {
    push(node, l, r);
    if(l == r) {
        if(t[node] <= val) return l;
        else return l+1;
    }
    int mid = (l + r) >> 1;
    if(t[node*2+1] <= val) return lb(node*2+1, l, mid, val);
    else return lb(node*2+2, mid+1, r, val);
}
int query(int node, int l, int r, int idx) {
    push(node, l, r);
    if(l > idx || r < idx) return inf;
    if(l == r) {
        return t[node];
    }
    int mid = (l + r) >> 1;
    return min(query(node*2+1, l, mid, idx), query(node*2+2, mid+1, r, idx));
}

void solve() {
    int n;
    cin >> n;
    vpi a(n);
    F(i, 0, n) cin >> a[i].fi >> a[i].se;
    sort(a.begin(), a.end());
    F(i, 0, n) {
        int r1 = a[i].fi;
        int first = query(0, 1, N-1, r1 - a[i].se + 1);
        int l1 = min(lb(0, 1, N-1, first-1), r1+1);
        int left = a[i].se - (r1 - l1 + 1);
        int l2 = lb(0, 1, N-1, first);
        int r2 = l2 + left - 1;
        //cout << first sp l1 sp r1 sp l2 sp r2 << endl;
        update(0, 1, N-1, l1, r1);
        update(0, 1, N-1, l2, r2);
    }
    int ans = 0;
    F(i, 1, N) {
        int get = query(0, 1, N-1, i);
        ans += get * (get-1) / 2;
    }
    cout << ans << endl;
}
 
void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Local
        freopen("local.in", "r", stdin);
        freopen("local.out", "w", stdout);
    #else 
        // freopen("poetry.in","r",stdin);
        // freopen("poetry.out","w",stdout);
    #endif
}
signed main() {
    setIO();
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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