oj.uz

Submission #963764

# Submission time Handle Problem Language Result Execution time Memory
963764 2024-04-15T15:50:26 Z Icelast Sails (IOI07_sails) C++17
100 / 100
 185 ms 6020 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e5+5, INF = 4e18+9;
int n;
struct mast{
    int h, k;
};
mast a[maxn];
bool cmp(mast a, mast b){
    return a.h < b.h;
}
void inp(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].h >> a[i].k;
    }
}
int N, T[4*maxn], lz[4*maxn], Tmx[4*maxn];
void build_segtree(){
    N = 1;
    while(N < 1e5){
        N*=2;
    }
}
void down(int node, int low, int high){
    int len = high-low+1;
    for(int child = node*2; child <= node*2+1; child++){
        if(child >= 2*N) continue;
        lz[child] += lz[node];
    }
    T[node]+=lz[node]*len;
    Tmx[node]+=lz[node];
    lz[node] = 0;
}
void upd(int node, int low, int high, int l, int r, ll x){
    if(r < l) return;
    down(node, low, high);
    if(low > r || l > high){
        return;
    }
    if(low >= l && r >= high){
        lz[node] += x;
        down(node, low, high);

        return;
    }
    int mid = (low+high)/2;
    upd(node*2, low, mid, l, r, x);
    upd(node*2+1, mid+1, high, l, r, x);
    T[node] = T[node*2]+T[node*2+1];
    Tmx[node] = max(Tmx[node*2], Tmx[node*2+1]);
}
int get_sum(int node, int low, int high, int l, int r){
    if(r < l) r = l;
    down(node, low, high);
    if(low > r || l > high){
        return 0;
    }
    if(low >= l && r >= high){
        return T[node];
    }
    int mid = (low+high)/2;
    return get_sum(node*2, low, mid, l, r)+get_sum(node*2+1, mid+1, high, l, r);
}
int get_max(int node, int low, int high, int l, int r){
    if(r < l) r = l;
    down(node, low, high);
    if(low > r || l > high){
        return 0;
    }
    if(low >= l && r >= high){
        return Tmx[node];
    }
    int mid = (low+high)/2;
    return max(get_max(node*2, low, mid, l, r), get_max(node*2+1, mid+1, high, l, r));
}
int get_pos(int node, int low, int high, ll k){
    if(low == high){
        if(Tmx[node] < k){
            return 0;
        }
        return low;
    }
    int mid = (low+high)/2;
    down(node, low, high);
    down(node*2, low, mid);
    down(node*2+1, mid+1, high);
    if(Tmx[node*2+1] >= k){
        return get_pos(node*2+1, mid+1, high, k);
    }else{
        return get_pos(node*2, low, mid, k);
    }
}
void solve(){
    sort(a+1, a+1+n, cmp);
    build_segtree();
    int M, k;
    for(int i = 1; i <= n; i++){
        M = a[i].h; k = a[i].k;
        ll x = get_sum(1, 1, N, M-k+1, M-k+1);
        int u = get_pos(1, 1, N, x);
        int d = get_pos(1, 1, N, x+1)+1;
        u = min(u, M);
        d = min(d, M);
        upd(1, 1, N, u+1, M, 1);
        upd(1, 1, N, d, d+u-(M-k+1), 1);
    }
    ll ans = 0;
    for(int i = 1; i <= M; i++){
        ll x = get_sum(1, 1, N, i, i);
        ans += x*(x-1)/2;
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inp();
    solve();
}

Compilation message

sails.cpp: In function 'void solve()':
sails.cpp:111:22: warning: 'M' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |     for(int i = 1; i <= M; i++){
      |                    ~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 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 1 ms 2512 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct
2 Correct 20 ms 3928 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3160 KB Output is correct
2 Correct 46 ms 3164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 4180 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 5268 KB Output is correct
2 Correct 135 ms 5412 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 5524 KB Output is correct
2 Correct 105 ms 4948 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 6020 KB Output is correct
2 Correct 131 ms 4804 KB Output is correct