oj.uz

Submission #114211

# Submission time Handle Problem Language Result Execution time Memory
114211 2019-05-31T10:00:51 Z zubec Sails (IOI07_sails) C++14
100 / 100
 203 ms 6532 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 11 ms 4864 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1920 KB Output is correct
2 Correct 41 ms 1016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3148 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 5604 KB Output is correct
2 Correct 185 ms 6532 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 5720 KB Output is correct
2 Correct 148 ms 6000 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 5756 KB Output is correct
2 Correct 117 ms 2800 KB Output is correct