Submission #114211

#	Time	Username	Problem	Language	Result	Execution time	Memory
114211		zubec	Sails (IOI07_sails)	C++14	100 / 100	203 ms	6532 KiB

sails

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

vector <pair<int, int> > vec;

int n;

const int N = 100100;

int bal[N], sz;

pair<int, int> ob[N*4], t[N*4];


void push(int v){
    if (ob[v].first == 0)
        return;
    t[v+v] = t[v+v+1] = ob[v+v] = ob[v+v+1] = ob[v];
    ob[v] = {0, 0};
}

void update(int v, int l, int r, int tl, int tr, pair<int, int> pr){
    if (l > r || tl > r || l > tr || tl > tr)
        return;
    if (tl <= l && r <= tr){
        t[v] = ob[v] = pr;
        return;
    }
    int mid = (l+r)>>1;
    push(v);
    update(v+v, l, mid, tl, tr, pr);
    update(v+v+1, mid+1, r, tl, tr, pr);
}

pair<int, int> get(int v, int l, int r, int pos){
    if (l == r)
        return t[v];
    int mid = (l+r)>>1;
    push(v);
    if (pos <= mid)
        return get(v+v, l, mid, pos); else
        return get(v+v+1, mid+1, r, pos);
}

void add(int pos, int x){
    if (bal[pos] == 0){
        bal[pos] += x;
        pair<int, int> pr = get(1, 1, sz, pos);
        update(1, 1, sz, pr.first, pos-1, {pr.first, pos-1});
        update(1, 1, sz, pos, pr.second, {pos, pr.second});
    } else
    if (bal[pos]+x == 0){
        pair<int, int> pr = get(1, 1, sz, pos-1);
        pair<int, int> pr2 = get(1, 1, sz, pos+1);
        pr.second = pos;
        if (bal[pos+1] == 0)
            pr.second = pr2.second;
        update(1, 1, sz, pr.first, pr.second, pr);
        bal[pos] += x;
    } else {
        bal[pos] += x;
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        int h, k;
        cin >> h >> k;
        vec.push_back({h, k});
    }
    sort(vec.begin(), vec.end());

    sz = 100010;

    for (int i = 0; i < vec.size(); i++){
        int h = vec[i].first;
        int k = vec[i].second;
        int l = h-k+1;
        if (i == 0){
            ++bal[1];
            --bal[k+1];
            update(1, 1, sz, 1, k, {1, k});
            update(1, 1, sz, k+1, sz, {k+1, sz});
        } else
        if (bal[l] == 0){
            pair<int, int> pr = get(1, 1, sz, l);
            int a = pr.first, b = min(h, pr.second);
            add(a, 1);
            add(a+b-l+1, -1);
            add(b+1, 1);
            add(h+1, -1);
        } else {
            add(l, 1);
            add(h+1, -1);
        }
    }
    ll lst = 0;
    ll ans = 0;
    for (int j = 1; j <= sz; j++){
        ll x = bal[j]+lst;
        ans += x*(x-1)/2;
        lst = x;
    }
    cout << ans;;

}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

• 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