oj.uz

Submission #392887

# Submission time Handle Problem Language Result Execution time Memory
392887 2021-04-22T07:16:50 Z Aldas25 Sails (IOI07_sails) C++14
40 / 100
 1000 ms 6964 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

const int MAXN = 100100;

int n;
vii seq;

ll cnt[MAXN];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
vector<pair<ll, int>> rem;

int main()
{
    FAST_IO;

    cin >> n;
    REP(n) {
        int h, k; cin >> h >> k;
        seq.pb({h, k});
    }
    sort(seq.begin(), seq.end());

    ll ans = 0;

    FOR(i, 0, n-1) {
        int lst = i==0 ? 0 : seq[i-1].f;
        int h = seq[i].f;
        int k = seq[i].s;
        FOR(j, lst+1, h) {
            q.push({0, j});
        }

        rem.clear();
        REP(k) {
            auto pp = q.top();
            q.pop();
            int j = pp.s;
            cnt[j]++;
            rem.pb({cnt[j], j});
        }
        for (auto pp : rem) q.push(pp);


        lst = h;
    }

    FOR(i, 0, MAXN-1) {
        if (cnt[i] == 0) continue;
        ans += (cnt[i] * (cnt[i]-1))/2;
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 14 ms 368 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 716 KB Output is correct
2 Correct 337 ms 3092 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 1236 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 1006 ms 1352 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 1712 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 6964 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 1090 ms 2508 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 1090 ms 2988 KB Time limit exceeded
2 Halted 0 ms 0 KB -