oj.uz

Submission #1022198

# Submission time Handle Problem Language Result Execution time Memory
1022198 2024-07-13T10:57:54 Z vjudge1 Fountain (eJOI20_fountain) C++17
30 / 100
 1500 ms 2900 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 r , v;
            cin >> r >> v;
            int i = r;
            for(int j = i; j <= n; ++j){
                if(pref[j] - pref[i - 1] >= v){
                    i = j;
                    break;
                }
            }
            if(i == n)cout << 0 << nl;
            else cout << i << 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1560 ms 2900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Execution timed out 1560 ms 2900 KB Time limit exceeded
9 Halted 0 ms 0 KB -