oj.uz

Submission #642475

# Submission time Handle Problem Language Result Execution time Memory
642475 2022-09-19T14:21:26 Z Carmel_Ab1 Fountain (eJOI20_fountain) C++17
100 / 100
 431 ms 41796 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}
vi nxt_greater(vi a){
    int n=a.size();
    vi nxt(n,-1);
    stack<int>S;

    for(int i=0; i<n; i++){
        while(S.size() && a[S.top()]<a[i]){
            nxt[S.top()]=i;
            S.pop();
        }
        S.push(i);
    }
    return nxt;
}

void solve() {
    int n,q;
    cin >> n >> q;
    vi D(n+1),C(n+1);
    for(int i=1; i<=n; i++)
        cin >> D[i] >> C[i];

    vi nxt_g= nxt_greater(D);
    int lg=18;

    vvl dp(n+1,vl(lg,1e18)),nxt(n+1,vl(lg,-1));//sum of first 2^j on path starts from i
    for(int i=1; i<=n; i++)
        nxt[i][0]=nxt_g[i],dp[i][0]=C[i];

    for(int j=1; j<lg; j++) {
        for (int i = 1; i <= n; i++)
            if (nxt[i][j - 1] != -1) {
                nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
                dp[i][j]=dp[i][j-1]+dp[nxt[i][j-1]][j-1];
            }
    }

    while(q--){
        int r,v;
        cin >> r >> v;
        int ans=r;
        for(int i=lg-1; i>=0; i--)
            if(dp[ans][i]<v)
                v-=dp[ans][i],ans=nxt[ans][i];

        if(!(ans!=-1 && C[ans]>=v))
            ans=0;
        cout << ans << "\n";
    }
}

Compilation message

fountain.cpp: In function 'void usaco(std::string)':
fountain.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 37388 KB Output is correct
2 Correct 321 ms 36568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 296 ms 37388 KB Output is correct
9 Correct 321 ms 36568 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 124 ms 23100 KB Output is correct
12 Correct 431 ms 41716 KB Output is correct
13 Correct 329 ms 41796 KB Output is correct
14 Correct 206 ms 41540 KB Output is correct
15 Correct 152 ms 41764 KB Output is correct