oj.uz

Submission #871877

# Submission time Handle Problem Language Result Execution time Memory
871877 2023-11-11T18:45:37 Z hqminhuwu Sails (IOI07_sails) C++14
0 / 100
 87 ms 13220 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){
    if (lazy[i] == 0)
        return;
    lazy[(i << 1)] += lazy[i];
    lazy[(i << 1) | 1] += lazy[i];
    treemin[(i << 1)] += lazy[i];
    treemin[(i << 1) | 1] += lazy[i];
    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);
    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);
    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;
    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){
    //    cout << a[i].st << " " << a[i].nd << "\n";
        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 << u << " " << p << " " << q << "\n";
        if (q == -1){
            update(1,1,n,p,p + a[i].nd - 1);
           // cout << p << " " << 
        }
        else {
            update(1,1,n,q,n);
            int lft = a[i].nd - (n - q + 1);
            update(1,1,n,p,p + lft - 1);
        }
    //    cout << ans << "\n";
    }
    cout << ans;
    return 0;
}
/*



*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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