oj.uz

Submission #1022215

# Submission time Handle Problem Language Result Execution time Memory
1022215 2024-07-13T11:11:04 Z vjudge1 Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 7824 KB 
#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.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6228 KB Output is correct
2 Correct 57 ms 6364 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 58 ms 6228 KB Output is correct
9 Correct 57 ms 6364 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1075 ms 3564 KB Output is correct
12 Correct 106 ms 7824 KB Output is correct
13 Execution timed out 1594 ms 4096 KB Time limit exceeded
14 Halted 0 ms 0 KB -