oj.uz

Submission #771219

# Submission time Handle Problem Language Result Execution time Memory
771219 2023-07-02T16:07:00 Z cnastea Fountain (eJOI20_fountain) C++14
60 / 100
 268 ms 4848 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){
        int r, v;
        for(int i = 0; i < q; i++){
            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];
        }
        for(int i = 0; i < q; i++){
            int r, v;
            cin >> r >> v;
            if(c[r-1]-v >= 0 && c[r-1]-v < c[n-1]) cout << n << "\n";
            else if(c[r-1]-v < 0) cout << 0 << "\n";
            else{
                int a = 0, b = n;
                while(b - a > 1){
                    int m = (a+b)/2;
                    if(c[r-1]-v < c[m]) a = m;
                    else b = m;
                }
                cout << b << "\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 2 ms 212 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 3 ms 312 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 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 4556 KB Output is correct
2 Correct 268 ms 4848 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 3 ms 312 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 212 KB Output is correct
8 Correct 237 ms 4556 KB Output is correct
9 Correct 268 ms 4848 KB Output is correct
10 Incorrect 4 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -