oj.uz

Submission #455177

# Submission time Handle Problem Language Result Execution time Memory
455177 2021-08-05T15:50:22 Z urosk Fountain (eJOI20_fountain) C++14
100 / 100
 422 ms 47928 KB 
///sat
#include <chrono>
using namespace std::chrono;
#define vremestart auto start = high_resolution_clock::now();
#define vremeend auto stop = high_resolution_clock::now();
#define vremeispis auto duration = duration_cast<microseconds>(stop - start); cout << duration.count() << endl;
///sat
#define here cerr<<"---------------------------\n"
#define popcount(x) __builtin_popcount(x) ///broj bitova
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define th third
#define fo fourth
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
using namespace std;
void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}

ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
#define maxn 100005
ll d[maxn];
ll c[maxn];
ll n,t;
ll g[maxn];
ll anc[maxn][25];
ll sum[maxn][25];
ll siz[maxn];
bool vis[maxn];
void dfs(ll u){
    vis[u] = 1;
    ll s = g[u];
    if(s==0) return;
    c[s] = c[u] + c[s];
    dfs(s);
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    ll r,v;
    cin >> r >> v;
    if(v<=c[r]){
        cout<<r<<endl;
        return;
    }
    v-=c[r];
    //cerr<<"v: "<<v<<endl;
    while(1){
        for(ll i = 0;i<25;i++){
            if(anc[r][i]==0){
                if(i==0){
                    cout<<0<<endl;
                    return;
                }
                v-=sum[r][i-1];
                r = anc[r][i-1];
                break;
            }
            if(v<sum[r][i]){
                if(i==0){
                    goto lol2;
                }
                v-=sum[r][i-1];
                r = anc[r][i-1];
                break;
            }
        }

    }
    lol2:;
    if(v!=0) cout<<g[r]<<endl;
    else cout<<r<<endl;
    return;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	cin >> n >> t;
	for(ll i = 1;i<=n;i++){
        cin >> d[i] >> c[i];
	}
	d[0] = 1000000000000000;
    stack<ll> s;
    for(ll i = 1;i<=n;i++){
        while(!s.empty()&&d[i]>d[s.top()]){
            g[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    for(ll i = 1;i<=n;i++){
        //cerr<<g[i]<<endl;
        anc[i][0] = g[i];
        sum[i][0] = c[g[i]];
    }
    for(ll i = 1;i<25;i++){
        for(ll j = 1;j<=n;j++){
            anc[j][i] = anc[anc[j][i-1]][i-1];
            sum[j][i] = sum[j][i-1] + sum[anc[j][i-1]][i-1];
        }
    }
    for(ll i = 1;i<=n;i++){
        for(ll j = 0;j<25;j++){
            if(anc[i][j]==0){
                siz[i] = j;
                goto lol;
            }
        }
        lol:;
        //cerr<<siz[i]<<" ";
    }
    //cerr<<endl;
    /*here;
    for(ll i = 1;i<=n;i++){
        for(ll j = 0;j<siz[j]+1;j++){
            cerr<<sum[i][j]<< " ";
        }
        cerr<<endl;
    }
    here;*/
    while(t--){
        tc();
    }
	return 0;
}
/*
10 3
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
3 5
8 5
2 4
*/

Compilation message

fountain.cpp: In function 'void setIO(std::string)':
fountain.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:33:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 41220 KB Output is correct
2 Correct 297 ms 38240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 282 ms 41220 KB Output is correct
9 Correct 297 ms 38240 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 120 ms 25344 KB Output is correct
12 Correct 422 ms 47776 KB Output is correct
13 Correct 319 ms 47472 KB Output is correct
14 Correct 206 ms 46640 KB Output is correct
15 Correct 171 ms 47928 KB Output is correct