Submission #871882

#	Time	Username	Problem	Language	Result	Execution time	Memory
871882		hqminhuwu	Sails (IOI07_sails)	C++14	100 / 100	147 ms	12372 KiB

sails

#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 / 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