oj.uz

Submission #770707

# Submission time Handle Problem Language Result Execution time Memory
770707 2023-07-01T18:48:09 Z cnastea Fountain (eJOI20_fountain) C++14
30 / 100
 1500 ms 323180 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> d(n+1), c(n);
    d[n] = 1000000001;
    for(int i = 0; i < n; i++){
        cin >> d[i] >> c[i];
    }
    if(n <= 1000 && q <= 2000){
        for(int i = 0; i < q; i++){
            int r, v;
            cin >> r >> v;
            int k = r-1, m = r-1;
            v -= c[m];
            while(v > 0 && m <= n && k < n){
                if(d[m] > d[k]){
                    v -= c[m];
                    k = m;
                }
                m++;
            }
            if(k == n) cout << 0 << "\n";
            else cout << k+1 << "\n";
        }
    }
    else{
        for(int i = n-2; i >= 0; i--){
            c[i] += c[i+1];
        }
        map<int, int> m;
        int k = n-1;
        for(int i = 0; i <= c[0]; i++){
            if(k > 0 && c[k] <= i){
                k--;
            }
            m[i] = k+1;
        }
        for(int i = 0; i < q; i++){
            int r, v;
            cin >> r >> v;
            if(m[c[r-1]-v] == n+1) cout << 0 << "\n";
            else cout << m[c[r-1]-v] << "\n";
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 323180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Execution timed out 1556 ms 323180 KB Time limit exceeded
9 Halted 0 ms 0 KB -