oj.uz

Submission #674018

# Submission time Handle Problem Language Result Execution time Memory
674018 2022-12-22T14:53:52 Z Cookie Sails (IOI07_sails) C++14
100 / 100
 125 ms 4208 KB 
#include<bits/stdc++.h>

#include<fstream>
//SUS
using namespace std;
ifstream fin("marathon.in");
ofstream fout("marathon.out");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mxn = 1e5, mxq = 200;
const ll p = 31, mod = 1e9 + 7;

const ll mxv = 1e9;
struct th{
    int h, k;
    bool operator <(const th &b){
        return(h < b.h);
    }
};
int mx[4 * mxn + 1], lz[4 * mxn + 1];
th a[mxn + 1];
int n;
void push(int nd){
    lz[nd * 2] += lz[nd]; lz[nd * 2 + 1] += lz[nd];
    mx[nd * 2] += lz[nd]; mx[nd * 2 + 1] += lz[nd];
    lz[nd] = 0;
    return;
}

int getv(int nd, int l, int r, int id){
    
    if(l == r){
        return(mx[nd]);
    }
    int mid = (l + r) >> 1;
    push(nd);
    if(id <= mid)return(getv(nd * 2, l, mid, id));
    else return(getv(nd * 2 + 1, mid + 1, r, id));
    
}
int getl(int nd, int l, int r, int k){
    if(mx[1] <= k)return(1);
    if(l == r)return(l + 1);
    int mid = (l + r) >> 1;
    push(nd);
    if(mx[nd * 2 + 1] > k){
        return(getl(nd * 2 + 1, mid + 1, r, k));
    }else{
        return(getl(nd * 2, l, mid, k));
    }
}
int getr(int nd, int l, int r, int k){
    if(l == r)return(l);
    int mid = (l + r) >> 1;
    push(nd);
    if(mx[nd * 2 + 1] >= k){
        return(getr(nd * 2 + 1, mid + 1, r, k));
    }else{
        return(getr(nd * 2, l, mid, k));
    }
}
void upd(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        mx[nd]++; lz[nd]++;
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd(nd * 2, l, mid, ql, qr); upd(nd * 2 + 1, mid + 1, r, ql, qr);
    mx[nd] = max(mx[nd * 2], mx[nd * 2 + 1]); 
}
void add(int h, int k){
    // find range [a, b]
    int var = getv(1, 1, mxn, h - k + 1); // value of range
    int l = getl(1, 1, mxn, var), r = getr(1, 1,  mxn, var);
    
    if(r == mxn){
        upd(1, 1, mxn, l, l + k - 1);
    }else{
    upd(1, 1, mxn, l, l + r - h + k - 1); upd(1, 1, mxn, r + 1, h);
    }
    
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i].h >> a[i].k;
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++)add(a[i].h, a[i].k);
    ll res = 0;
    for(int i = 1; i <= mxn; i++){
        ll v = getv(1, 1, mxn, i);
        
        res += (v * (v - 1)) / 2;
    }
    cout << res;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2388 KB Output is correct
2 Correct 8 ms 2388 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2400 KB Output is correct
2 Correct 8 ms 2388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2388 KB Output is correct
2 Correct 8 ms 2384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2388 KB Output is correct
2 Correct 8 ms 2388 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2388 KB Output is correct
2 Correct 10 ms 2416 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2516 KB Output is correct
2 Correct 43 ms 2892 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3032 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3224 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3820 KB Output is correct
2 Correct 104 ms 3876 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4068 KB Output is correct
2 Correct 60 ms 3784 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4208 KB Output is correct
2 Correct 98 ms 4112 KB Output is correct