oj.uz

Submission #871882

# Submission time Handle Problem Language Result Execution time Memory
871882 2023-11-11T19:05:52 Z hqminhuwu Sails (IOI07_sails) C++14
100 / 100
 147 ms 12372 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

ll treemin[4 * N],treesum[4 * N],lazy[4 * N];
void down (int i, int l, int r){
    if (lazy[i] == 0)
        return;
    int mid = (r + l) >> 1;
    lazy[(i << 1)] += lazy[i];
    lazy[(i << 1) | 1] += lazy[i];
    treemin[(i << 1)] += lazy[i];
    treemin[(i << 1) | 1] += lazy[i];
    treesum[(i << 1)] += lazy[i] * (mid - l + 1);
    treesum[(i << 1) | 1] += lazy[i] * (r - mid);
    lazy[i] = 0;
}

void update (int i, int l, int r, int u, int v){
    if (l > v || r < u)
        return;
    if (l >= u && r <= v){
        lazy[i] ++;
        treemin[i]++;
        treesum[i] += (r - l + 1);
        return;
    }
    down(i,l,r);
    int mid = (l + r) >> 1;
    update ((i << 1), l, mid, u, v);
    update ((i << 1) | 1, mid + 1, r ,u, v);
    treemin[i] = min (treemin[(i << 1)], treemin[(i << 1) | 1]);
    treesum[i] = (treesum[(i << 1)] + treesum[(i << 1) | 1]);
}

ll getsum (int i, int l, int r, int u, int v){
    if (l > v || r < u)
        return 0;
    if (l >= u && r <= v)
        return treesum[i];
    down(i,l,r);
    int mid = (l + r) >> 1;
    return (getsum ((i << 1), l, mid, u, v) + 
    getsum ((i << 1) | 1, mid + 1, r ,u, v));
}

ll walk (int i, int l, int r, ll val){
    if (treemin[i] > val) return -1;
    if (l == r) return l;
    down(i,l,r);
    int mid = (l + r) >> 1;
    if (treemin[(i << 1)] <= val)
        return walk(i << 1, l, mid, val);
    return walk((i << 1) | 1, mid + 1, r, val);
}

ll ans,n = 100000,i,m;
pll a[N];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m;
    forr (i,1,m)
        cin >> a[i].st >> a[i].nd;
    sort(a + 1, a + 1 + m);
    forr (i,1,m){
        ans += getsum(1,1,n,a[i].st - a[i].nd + 1,a[i].st);
        int u = getsum(1,1,n,a[i].st - a[i].nd + 1,a[i].st - a[i].nd + 1);
        int p = walk(1,1,n,u);
        int q = walk (1,1,n,u - 1);
        //cout << a[i].st << " " << a[i].nd << " " << u << " " << p << " " << q << "\n";
        if (q > a[i].st || q == -1 || q == p){
            update(1,1,n,p,p + a[i].nd - 1);
          //  cout << p << " " << p + a[i].nd - 1 << "\n"; 
        }
        else {
            update(1,1,n,q,a[i].st);
            int lft = a[i].nd - (a[i].st - q + 1);
            update(1,1,n,p,p + lft - 1);
          //  cout << p << " " << p + lft - 1 << " " << q << " " << a[i].st << "\n";
        }
    //    cout << ans << "\n";
    }
    cout << ans;
    return 0;
}
/*



*/

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 4 ms 9380 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4188 KB Output is correct
2 Correct 35 ms 7132 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8076 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8752 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 10272 KB Output is correct
2 Correct 87 ms 12372 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 10832 KB Output is correct
2 Correct 69 ms 11128 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10380 KB Output is correct
2 Correct 88 ms 9044 KB Output is correct