제출 #576473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
576473		mohammedMonem	Fountain (eJOI20_fountain)	C++14	60 / 100	1571 ms	3216 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40