oj.uz

Submission #908198

# Submission time Handle Problem Language Result Execution time Memory
908198 2024-01-16T09:24:37 Z zyq181 Fountain (eJOI20_fountain) C++17
100 / 100
 200 ms 19360 KB 
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define int long long 
const int MOD = 998244353;

//stack: value, suff

int N,Q;
int inp1, inp2;
vector<pair<int, int> > v; //reversed original {d, c}
vector<pair<int, pair<int, int> > > s; //{d, {suff, idx} }
vector<pair<int, pair<int, int> > > q; //sorted in decreasing index {idx, {wtr, qid} }

int ans[200010];

int32_t main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    cin >> N >> Q;
    for(int a=0; a<N; a++){
        cin >> inp1 >> inp2;
        v.push_back({inp1, inp2});
    }
    reverse(v.begin(), v.end());
    for(int a=0; a<Q; a++){
        cin >> inp1 >> inp2;
        q.push_back({inp1, {inp2, a}});
    }
    sort(q.begin(), q.end());
    for(int a=0; a<N; a++){
        //cout << "OK";
        int d, c;
        tie(d, c) = v[a];
        while(!s.empty() && s.back().first <= d){
            s.pop_back();
        }
        if(s.empty()){
            s.push_back({d, {c, N - a}});
        }
        else{
            int k = s.back().second.first;
            s.push_back({d, {c + k, N - a}});
        }
        /*
        cout << "AT " << N - a << " the stack is: \n";
        for(auto it: s){
            cout << it.first << ' ' << it.second.first << ' ' << it.second.second << '\n';
        } 
        cout << "\n\n";
        */
        while(!q.empty() && q.back().first == (N - a)){
            int qv = q.back().second.first;
            int id = q.back().second.second;
            q.pop_back();
            if(s.back().second.first < qv) ans[id] = 0;
            else{
                int lo = 0;
                int hi = s.size() - 1;
                int tot = s.back().second.first;
                while(lo < hi){
                    int mid = (lo + hi)/2;
                    if(tot - s[mid].second.first >= qv){
                        lo = mid + 1;
                    }
                    else{
                        hi = mid;
                    }
                }
                ans[id] = s[lo].second.second;
            }
        }
    }
    for(int a=0; a<Q; a++){
        cout << ans[a] << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 12252 KB Output is correct
2 Correct 147 ms 16876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 132 ms 12252 KB Output is correct
9 Correct 147 ms 16876 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 80 ms 7224 KB Output is correct
12 Correct 200 ms 19360 KB Output is correct
13 Correct 170 ms 14424 KB Output is correct
14 Correct 161 ms 13744 KB Output is correct
15 Correct 149 ms 15324 KB Output is correct