Submission #423147

#	Time	Username	Problem	Language	Result	Execution time	Memory
423147		EndRay	Sails (IOI07_sails)	C++17	5 / 100	103 ms	11588 KiB

sails

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+1;

int getrand(){
    return rand()<<16+rand();
}

struct node{
    int x, y;
    int cnt, sz;
    int add;
    node *l, *r;
    void push(){
        x += add;
        if(l) l->add += add;
        if(r) r->add += add;
        add = 0;

    }
    void apply(int k){
        add += k;
        push();
    }
    void upd(){
        sz = cnt + (l ? l->sz : 0) + (r ? r->sz : 0);
    }
    node(int x, int cnt=1, node *l=nullptr, node *r=nullptr):x(x), cnt(cnt), l(l), r(r), add(0){
        upd();
        y = getrand();
    }
};

int get_sz(node* t){
    return t ? t->sz : 0;
}

void split(node *t, node *&l, node *&r, int x){ /// (-inf, x) -> l, [x, inf) -> r
    if(!t){
        l = r = nullptr;
        return;
    }
    t->push();
    if(t->x >= x){
        split(t->l, l, t->l, x);
        r = t;
    }
    else{
        split(t->r, t->r, r, x);
        l = t;
    }
    if(l) l->upd();
    if(r) r->upd();
}

int found_x;
void split_sz(node *t, node *&l, node *&r, int sz){ /// size(-inf, x] == sz -> l, [x, inf) -> r
    if(!t){
        l = r = nullptr;
        return;
    }
    t->push();
    int l_sz = get_sz(t->l);
    if(l_sz >= sz){
        split_sz(t->l, l, t->l, sz);
        r = t;
    }
    else if(l_sz < sz && l_sz + t->cnt >= sz){
        r = new node(t->x, t->cnt-(sz-l_sz), nullptr, t->r);
        l = t;
        l->cnt = sz-l_sz;
        l->r = nullptr;
        found_x = t->x;
    }
    else{
        split_sz(t->r, t->r, r, sz - l_sz - t->cnt);
        l = t;
    }
    if(l) l->upd();
    if(r) r->upd();
}

void merge(node *&t, node *l, node *r){
    if(!l || !r){
        t = (l ? l : r);
        return;
    }
    l->push();
    r->push();
    if(l->y > r->y){
        merge(l->r, l->r, r);
        t = l;
    }
    else{
        merge(r->l, l, r->l);
        t = r;
    }
    t->upd();
}

void add_cnt(node *&t, int x, int cnt){
    if(!t){
        t = new node(x, cnt);
        return;
    }
    if(t->x > x)
        add_cnt(t->l, x, cnt);
    else if(t->x == x)
        t->cnt += cnt;
    else add_cnt(t->r, x, cnt);
    t->upd();
}

void add(node *&t, int sz){
    node *ll, *lr, *rl, *rr;
    split_sz(t, ll, rr, sz);
    split(ll, ll, lr, found_x);
    split(rr, rl, rr, found_x+1);
    add_cnt(rr, found_x+1, get_sz(lr));
    add_cnt(ll, found_x-1, get_sz(rl));
    ll->apply(1);
    merge(t, ll, rr);
}

long long ans(node *t){
    if(!t) return 0;
    return ans(t->l) + 1ll*t->x*(t->x-1)/2*t->cnt + ans(t->r);
}

void print(node *t){
    if(!t) return;
    t->push();
    print(t->l);
    print(t->r);
}

int n;
pair<int, int> p[N];

int main(){
    srand(time(NULL));
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> p[i].first >> p[i].second;
    sort(p, p+n);
    node *t = new node(0, 0);
    for(int i = 0; i < n; ++i){
        add_cnt(t, 0, p[i].first - t->sz);
        add(t, p[i].second);
    }
    cout << ans(t) << "\n";
}

Compilation message (stderr)

sails.cpp: In function 'int getrand()':
sails.cpp:8:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    8 |     return rand()<<16+rand();
      |                    ~~^~~~~~~
sails.cpp: In constructor 'node::node(int, int, node*, node*)':
sails.cpp:15:15: warning: 'node::r' will be initialized after [-Wreorder]
   15 |     node *l, *r;
      |               ^
sails.cpp:14:9: warning:   'int node::add' [-Wreorder]
   14 |     int add;
      |         ^~~
sails.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     node(int x, int cnt=1, node *l=nullptr, node *r=nullptr):x(x), cnt(cnt), l(l), r(r), add(0){
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10