Submission #1246972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246972		al_reem_2010	Fountain (eJOI20_fountain)	C++20	100 / 100	239 ms	72024 KiB

fountain

// اَللَهُمَ صَلِ عَلَىَ مُحَمَدٍ وَ آلِ مُحَمَدٍ
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <thread>
#include <fstream>
#include <stack>
using namespace std ;
#define int long long
#define pb push_back
#define si size()
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define applejuice ios::sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
const int inf=1e18 ;
const int mod=1e9+7 ;
const int maxn=1e5+7 ;
const int sz=1<<17 ;
int tt=1 , e=inf ;
struct T{
    int d ;
    int c ;
} ;
int d[maxn] , c[maxn] , d2[maxn] , seg[maxn*4] ;
T an[31][maxn] ;
set<int> val ;
map<int,int> nval ;
vector<int> v[maxn] ;
void update(int x)
{
    int k=x ;
    x+=sz ;
    seg[x]=k ;
    for(x/=2 ; x>0 ; x/=2) {seg[x]=min(seg[x*2],seg[x*2+1]) ;}
}
int get(int l, int r, int lo=0, int hi=sz-1, int x=1)
{
    if(hi<l || r<lo) {return e ;}
    if(l<=lo && hi<=r) {return seg[x] ;}
    int mid=(lo+hi)/2 ;
    int segl=get(l,r,lo,mid,x*2) ;
    int segr=get(l,r,mid+1,hi,x*2+1) ;
    return min(segl,segr) ;
}
void solve()
{
    int n , q ;
    cin >> n >> q ;
    for(int i=1 ; i<=n ; i++) {cin >> d[i] >> c[i] ; val.insert(d[i]) ;}
    // compression
    int k=0 ;
    for(auto i:val) {nval[i]=k ; k+=1 ;}
    for(int i=1 ; i<=n ; i++) {d[i]=nval[d[i]] ; v[d[i]].pb(i) ;}
    // segment tree
    for(int i=0 ; i<maxn*4 ; i++) {seg[i]=inf ;}
    for(int i=n-1 ; i>=0 ; i--)
    {
        for(int j=0 ; j<v[i].si ; j++)
        {
            d2[v[i][j]]=get(v[i][j],n) ;
            if(d2[v[i][j]]==inf) {d2[v[i][j]]=0 ;}
        }
        for(int j=0 ; j<v[i].si ; j++) {update(v[i][j]) ;}
    }
    // binary lefting
    for(int j=1 ; j<=n ; j++) {an[0][j]={d2[j],c[j]} ;}
    for(int i=1 ; i<=30 ; i++)
    {
        for(int j=0 ; j<n ; j++)
        {
            int mid=an[i-1][j].d ;
            an[i][j].d=an[i-1][mid].d ;
            an[i][j].c=an[i-1][j].c+an[i-1][mid].c ;
        }
    }
    while(q--)
    {
        int r , v ;
        cin >> r >> v ;
        for(int i=30 ; i>=0 ; i--)
        {
            if(v-an[i][r].c>0)
            {
                v-=an[i][r].c ;
                r=an[i][r].d ;
            }
        }
        cout << r << "\n" ;
    }
}
signed main()
{
    //wrong
    applejuice ;
    //cin >> tt ;
    while(tt--) {solve() ;}
}
/*
 6 5
 4 10
 6 8
 3 5
 4 14
 10 9
 4 20
 1 25
 6 30
 5 8
 3 13
 2 8
 output :
 5
 0
 5
 4
 2
 */

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40