제출 #1022215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022215		vjudge1	Fountain (eJOI20_fountain)	C++17	60 / 100	1594 ms	7824 KiB

fountain

#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define str string
#define pb push_back
#define pf push_front
#define nl "\n"
#define ll long long
#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
#define len(a) a.size()
// #define sz(v) (int)(v.size())
#define pii pair<int,int>
const int N = 1e6 + 1;
const int md = 998244353;
const int MOD = 1e9 + 7;
const int mega = 1e6 + 3;
const int inf = 1e9;
ll gcd(int a, int b){
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
ll lcm(int a, int b){
    return (a / gcd(a, b)) * b;
}
int d[100100 + 1] , c[100100 + 1];
void solve(){
    int n , q;
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)cin >> d[i] >> c[i];
    bool fl = 0;
    for(int i = 1; i < n; ++i)if(d[i] >= d[i + 1])fl = 1;
    if(fl == 0){
        int pref[n + 1];
        pref[0] = 0;
        for(int i = 1; i <= n; ++i)pref[i] = pref[i - 1] + c[i];
        while(q--){
            int rx , v;
            cin >> rx >> v;
            int i = rx;
            int l = i , r = n , res = 0 , mn = pref[i - 1];
            while(l <= r){
                int mid = (l + r) / 2;
                if(pref[mid] - mn >= v){
                    res = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            cout << res << nl;
        }
    }
    else{
    while(q--){
        int r , v;
        cin >> r >> v;
        int i = r;
        v -= c[i];
        while(v > 0){
            int x = n;
            for(int j = i + 1; j <= n; ++j){
                if(d[i] < d[j]){
                    x = j;
                    v -= c[j];
                    break;
                }
            }
            if(x == n){
                i = 0;
                break;
            }
            else{
                i = x;
            }
        }
        cout << i << nl;
    }
    }
}
signed main(){
    // freopen("haircut.in", "r", stdin);
    // freopen("haircut.out", "w", stdout);
    SPEED;
    int t = 1;
    //cin >> t;
    while (t--) {
        //t2++;
        //cout << "Case " << t2 << ": ";
        solve();
        // cout << nl;
        // t2++;
        //cout << nl;
    }
    #ifndef ONLINE_JUDGE
    cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40