Submission #1061570

#TimeUsernameProblemLanguageResultExecution timeMemory
1061570new_accEscape Route 2 (JOI24_escape2)C++14
0 / 100
1846 ms88916 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; const int N=1e6+10; const int SS=1<<19; const int INFi=2e9; const ll INFl=1e16; const ll mod2=998244353; const ll mod=1e9+7; const ll mod3=2027865967; const ll p=70032301; const ull p2=913; const int L=20; int n,m; vector<pair<int,int>> t[N]; vi t2[N]; pair<int,ll> jp[N][L]; pair<int,int> num[N]; map<pair<int,int>, ll> mm; ll zn(int a,int b){ ll res=0,curr=0; int g=0; b--; for(int i=L-1;i>=0;i--){ if(num[jp[a][i].fi].fi>=b) res=curr+jp[a][i].se,g=jp[a][i].fi; else{ curr+=jp[a][i].se; a=jp[a][i].fi; } } res+=t[b][num[g].se].se-t[b][num[g].se].fi; return res; } void solve(){ cin>>n>>m; vector<pair<int,int>> cr; int li=0; for(int i=1;i<n;i++){ int a; cin>>a; cr.clear(); while(a--){ int x,d; cin>>x>>d; cr.push_back({x,d}); } sort(cr.begin(),cr.end()); reverse(cr.begin(),cr.end()); while(cr.size()){ while(t[i].size() and t[i].back().se>cr.back().se) t[i].pop_back(); t[i].push_back(cr.back()); cr.pop_back(); } for(int i2=0;i2<t[i].size();i2++){ t2[i].push_back(++li); num[li]={i,i2}; } } num[li+1].fi=n; for(int i=0;i<L;i++) jp[li+1][i].fi=li+1; for(int i=1;i<n;i++){ int curr=0; for(int i2=0;i2<t[i].size();i2++){ while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++; ll xd=t[i][i2].se-t[i][i2].fi; if(curr==t[i+1].size()){ if(i<n-1) xd+=m-t[i][i2].se+t[i+1][0].fi,jp[t2[i][i2]][0].fi=t2[i+1][0]; else jp[t2[i][i2]][0].fi=li+1; }else{ xd+=t[i+1][curr].fi-t[i][i2].se; jp[t2[i][i2]][0].fi=t2[i+1][curr]; } jp[t2[i][i2]][0].se=xd; } } for(int i2=1;i2<L;i2++){ for(int i=1;i<=li;i++){ int g=jp[i][i2].fi; jp[i][i2].se=jp[i][i2-1].se+jp[jp[i][i2-1].fi][i2-1].se; jp[i][i2].fi=jp[jp[i][i2-1].fi][i2-1].fi; } } int q; cin>>q; for(int i=1;i<=q;i++){ int a,b; cin>>a>>b; if(mm.count(make_pair(a,b))>0){ cout<<mm[make_pair(a,b)]<<"\n"; continue; } ll res=INFl; for(auto u:t2[a]) res=min(res,zn(u,b)); mm[make_pair(a,b)]=res; cout<<res<<"\n"; } } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int tt=1; while(tt--) solve(); }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:60:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
      |                   ~~~~^~~~~~~~~~~~~~
Main.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             if(curr==t[i+1].size()){
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:84:17: warning: unused variable 'g' [-Wunused-variable]
   84 |             int g=jp[i][i2].fi;
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...