oj.uz

Submission #749287

# Submission time Handle Problem Language Result Execution time Memory
749287 2023-05-27T17:10:10 Z divad Fountain (eJOI20_fountain) C++14
100 / 100
 317 ms 20212 KB 
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int NMAX = 2e5+2;
int n,q,d,c,r,v,vf,aib[NMAX],sol[NMAX];
pair<int, int> a[NMAX];
int stv[NMAX];
vector<pair<int, int>> queries[NMAX];
 
void update(int pos, int val){
    for(int i = pos; i <= n; i += (i&-i)){
        aib[i] += val;
    }
}
 
int query(int pos){
    int ans = 0;
    for(int i = pos; i > 0; i -= (i&-i)){
        ans += aib[i];
    }
    return ans;
}
 
int range(int st, int dr){
    return query(dr)-query(st-1);
}
 
signed main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> d >> c;
        a[i] = {d, c};
    }
    for(int i = 1; i <= q; i++){
        cin >> r >> v;
        queries[r].push_back({v, i});
    }
    for(int i = n; i >= 1; i--){
        while(vf > 0 && a[stv[vf]].first <= a[i].first){
            update(vf, -a[stv[vf]].second);
            vf--;
        }
        stv[++vf] = i;
        update(vf, a[i].second);
        for(auto [val, idx]: queries[i]){
            int st = 1, dr = vf;
            int len = 0;
            while(st <= dr){
                int mid = (st+dr)/2;
                if(range(vf-mid+1, vf) >= val){
                    len = mid;
                    dr = mid-1;
                }else{
                    st = mid+1;
                }
            }
            if(len == 0){
                sol[idx] = 0;
            }else{
                sol[idx] = stv[vf-len+1];
            }
        }
    }
    for(int i = 1; i <= q; i++){
        cout << sol[i] << "\n";
    }
    return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:46:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         for(auto [val, idx]: queries[i]){
      |                  ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5016 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 5 ms 5076 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 8 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 13344 KB Output is correct
2 Correct 231 ms 16556 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5016 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 5 ms 5076 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 8 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 217 ms 13344 KB Output is correct
9 Correct 231 ms 16556 KB Output is correct
10 Correct 5 ms 5156 KB Output is correct
11 Correct 143 ms 11368 KB Output is correct
12 Correct 317 ms 20212 KB Output is correct
13 Correct 277 ms 18308 KB Output is correct
14 Correct 218 ms 17372 KB Output is correct
15 Correct 218 ms 17784 KB Output is correct