Submission #674018

#	Time	Username	Problem	Language	Result	Execution time	Memory
674018		Cookie	Sails (IOI07_sails)	C++14	100 / 100	125 ms	4208 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10