oj.uz

Submission #576473

# Submission time Handle Problem Language Result Execution time Memory
576473 2022-06-13T06:28:07 Z mohammedMonem Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 3216 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define space ' '
const int N = (int)1e5 + 20;

void Run(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 #ifndef ONLINE_JUDGE
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
 #endif
}
string s,t;

int main()
{
    Run();
    //vars&input
    int t = 1;
//    cin >> t;
    while (t--) {
        int n,q;
        cin >> n >> q;
        vector<pair<int,int>> reservoir(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> reservoir[i].first >> reservoir[i].second;
        bool isSorted = true;
        for (int i = 1; i < n; i++)
            if (reservoir[i].first < reservoir[i - 1].first)
                isSorted = false;
        
        if (isSorted) {
            ll prefix[N] = {0};
            for (int i = 1; i <= n; i++)
                prefix[i] = prefix[i - 1] + reservoir[i].second;
            while (q--) {
                int r,v;
                cin >> r >> v;
                int ans = 0;
                int s = r,e = n;
                while (s <= e) {
                    int mid = (s + e) / 2;
                    if (prefix[mid] - prefix[r - 1] >= v) {
                        ans = mid;
                        e = mid - 1;
                    }
                    else s = mid + 1;
                }
                cout << ans << endl;
            }
            return 0;
        }
        
        while (q--) {
            int r,v;
            cin >> r >> v;
            
            //operations room
            int mx = 0;
            for (int i = r; i <= n; i++) {
                if (reservoir[i].first > mx) {
                    mx = reservoir[i].first;
                    v -= reservoir[i].second;
                }
                if (v <= 0) {
                    //output
                    cout << i << endl;
                    break;
                }
            }
            if (v > 0) cout << 0 << endl;
        }
                
    }
    
    return 0;
    
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2488 KB Output is correct
2 Correct 85 ms 2564 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 66 ms 2488 KB Output is correct
9 Correct 85 ms 2564 KB Output is correct
10 Correct 2 ms 1108 KB Output is correct
11 Execution timed out 1571 ms 3216 KB Time limit exceeded
12 Halted 0 ms 0 KB -