Submission #455173

#	Time	Username	Problem	Language	Result	Execution time	Memory
455173		urosk	Fountain (eJOI20_fountain)	C++14	0 / 100	278 ms	41176 KiB

fountain

///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:;
    cout<<g[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;
}

Compilation message (stderr)

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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40