oj.uz

Submission #114251

# Submission time Handle Problem Language Result Execution time Memory
114251 2019-05-31T14:59:18 Z nvmdava Sails (IOI07_sails) C++17
30 / 100
 1000 ms 4080 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

#define N 131072
#define inf 250000
int seg[N << 1];
int cnt[N + 2];

vector<pii> fru;
vector<pii> upd;

void update(int x, int val){
    cnt[x] = val;
    x = x + N - 1;
    seg[x] = x - N + 1;
    x >>= 1;
    while(x){
        int l, r;
        l = seg[x << 1];
        r = seg[x << 1 | 1];
        if(cnt[l] > cnt[r])
            seg[x] = r;
        else
            seg[x] = l;
        x >>= 1;
    }
}

int query(int id, int l, int r, int L, int R){
    if(l >= L && R >= r) return seg[id];
    if(l > R || r < L) return 0;

    int m = (l + r) >> 1;
    int ll = query(id << 1, l, m, L, R);
    int rr = query(id << 1 | 1, m + 1, r, L, R);
    if(ll * rr == 0) return ll + rr;
    if(cnt[ll] > cnt[rr]) return rr;
    return ll;
}



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

    int n;
    for(int i = 1; i <= N; i++)
        update(i, 0);

    cin>>n;
    fru.resize(n);

    for(int i = 0; i < n; i++)
        cin>>fru[i].ff>>fru[i].ss;
//    cerr<<'\n';
    sort(fru.begin(), fru.end());

    for(auto s : fru){
//        cerr<<s.ff<<' '<<s.ss<<"\n";
        while(s.ss--){
            int x = query(1, 1, N, 1, s.ff);
//            cerr<<x<<' ';
            upd.push_back({x, cnt[x] + 1});
            update(x, inf);
        }
//        cerr<<'\n'<<'\n';
        while(!upd.empty()){
            update(upd.back().ff, upd.back().ss);
            upd.pop_back();
        }
    }

    long long res = 0;

    for(int i = 1; i < N; i++){
        res += 1LL * cnt[i] * (cnt[i] - 1) / 2;
    }
    cout<<res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Correct 7 ms 1920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Correct 7 ms 1920 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 KB Output is correct
2 Correct 8 ms 1920 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1920 KB Output is correct
2 Correct 48 ms 1920 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 2300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 2668 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 2944 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 4080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 3208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 3360 KB Time limit exceeded
2 Halted 0 ms 0 KB -