oj.uz

Submission #878444

# Submission time Handle Problem Language Result Execution time Memory
878444 2023-11-24T11:25:20 Z deadeye0 Sails (IOI07_sails) C++17
55 / 100
 37 ms 10440 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<ll,int> pi;
typedef tuple<int,int,int> ti;  
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 100010;
int n;
int h[N], k[N];
int ans[N];
ll total, ret;
multiset<pi> st;

ll fw[N], fw2[N];
void update(int x, int y, ll v) { 
    for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
ll sum (int x) {
    ll res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
ll query(int x, int y) { //inclusive
    return sum(y)-sum(x-1);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n;
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        cin >> h[i] >> k[i];
        total += k[i];
        chmax(mx, h[i]);
    }
    for (int i = 0; i < n; ++i) update(1, h[i], 1);
    for (int i = 1; i <= mx; ++i) st.insert({query(i, i), i});
    int cur = 0;
    while (1) {
        int rows = st.size();
        if (total >= rows) {
            total -= rows;
            ++cur;
        } else {
            int df = rows - total;
            while (df) {
                ans[st.begin()->si] = cur;
                st.erase(st.find(*st.begin()));
                --df;
            }
            for (auto i: st) ans[i.si] = cur + 1;
            break;
        }   
        while (st.size() && st.begin()->fi == cur) {
            ans[st.begin()->si] = cur;
            st.erase(st.find(*st.begin()));
        }
    }
    for (int i = 1; i <= mx; ++i) {
        ll val = ans[i] * (ans[i] + 1) / 2 - ans[i];
        ret += val;
    }
    cout << ret;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 19 ms 8852 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4952 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 9908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10252 KB Output is correct
2 Correct 37 ms 10236 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 10440 KB Output isn't correct
2 Halted 0 ms 0 KB -