oj.uz

Submission #799025

# Submission time Handle Problem Language Result Execution time Memory
799025 2023-07-31T08:48:18 Z bachhoangxuan Railway Trip (JOI17_railway_trip) C++17
100 / 100
 289 ms 36032 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=100005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=18;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=104729;
void solve(){
    int n,k,q;cin >> n >> k >> q;
    vector<int> a(n+1);
    vector<vector<pii>> p(n+1,vector<pii>(maxl,{0,0}));
    for(int i=1;i<=n;i++) cin >> a[i];
    vector<int> v;
    for(int i=1;i<=n;i++){
        while(!v.empty() && a[v.back()]<a[i]) v.pop_back();
        p[i][0].fi=(v.empty()?i:v.back());
        v.push_back(i);
    }
    v.clear();
    for(int i=n;i>=1;i--){
        while(!v.empty() && a[v.back()]<a[i]) v.pop_back();
        p[i][0].se=(v.empty()?i:v.back());
        v.push_back(i);
    }
    auto unions = [&](pii x,pii y){
        return make_pair(min(x.fi,y.fi),max(x.se,y.se));
    };
    for(int i=1;i<maxl;i++){
        for(int j=1;j<=n;j++) p[j][i]=unions(p[p[j][i-1].fi][i-1],p[p[j][i-1].se][i-1]);
    }
    for(int i=1;i<=q;i++){
        int s,t;cin >> s >> t;
        if(s>t) swap(s,t);
        int l=s,r=s,ans=0;
        for(int j=maxl-1;j>=0;j--){
            if(max(p[l][j].se,p[r][j].se)<t){
                ans+=(1<<j);
                tie(l,r)=unions(p[l][j],p[r][j]);
            }
        }
        int m=r;l=r=t;
        for(int j=maxl-1;j>=0;j--){
            if(min(p[l][j].fi,p[r][j].fi)>m){
                ans+=(1<<j);
                tie(l,r)=unions(p[l][j],p[r][j]);
            }
        }
        cout << ans << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 54 ms 33580 KB Output is correct
3 Correct 39 ms 33556 KB Output is correct
4 Correct 39 ms 33492 KB Output is correct
5 Correct 40 ms 33500 KB Output is correct
6 Correct 38 ms 33484 KB Output is correct
7 Correct 46 ms 33712 KB Output is correct
8 Correct 39 ms 34556 KB Output is correct
9 Correct 43 ms 34432 KB Output is correct
10 Correct 40 ms 34772 KB Output is correct
11 Correct 40 ms 34364 KB Output is correct
12 Correct 43 ms 34352 KB Output is correct
13 Correct 58 ms 34368 KB Output is correct
14 Correct 41 ms 34352 KB Output is correct
15 Correct 41 ms 34348 KB Output is correct
16 Correct 53 ms 34292 KB Output is correct
17 Correct 40 ms 33708 KB Output is correct
18 Correct 42 ms 33800 KB Output is correct
19 Correct 39 ms 33812 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 35132 KB Output is correct
2 Correct 149 ms 35148 KB Output is correct
3 Correct 148 ms 35144 KB Output is correct
4 Correct 125 ms 35148 KB Output is correct
5 Correct 130 ms 35092 KB Output is correct
6 Correct 124 ms 35100 KB Output is correct
7 Correct 134 ms 35140 KB Output is correct
8 Correct 200 ms 35564 KB Output is correct
9 Correct 227 ms 36032 KB Output is correct
10 Correct 289 ms 36000 KB Output is correct
11 Correct 231 ms 36020 KB Output is correct
12 Correct 249 ms 35952 KB Output is correct
13 Correct 234 ms 36032 KB Output is correct
14 Correct 213 ms 35320 KB Output is correct
15 Correct 171 ms 35064 KB Output is correct
16 Correct 134 ms 34904 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 35132 KB Output is correct
2 Correct 107 ms 35100 KB Output is correct
3 Correct 111 ms 35128 KB Output is correct
4 Correct 117 ms 35104 KB Output is correct
5 Correct 228 ms 35976 KB Output is correct
6 Correct 185 ms 35892 KB Output is correct
7 Correct 226 ms 35948 KB Output is correct
8 Correct 209 ms 35964 KB Output is correct
9 Correct 148 ms 35788 KB Output is correct
10 Correct 152 ms 35752 KB Output is correct
11 Correct 146 ms 35788 KB Output is correct
12 Correct 149 ms 35788 KB Output is correct
13 Correct 151 ms 35892 KB Output is correct
14 Correct 181 ms 35796 KB Output is correct
15 Correct 182 ms 35828 KB Output is correct
16 Correct 181 ms 35876 KB Output is correct
17 Correct 152 ms 35664 KB Output is correct
18 Correct 192 ms 35744 KB Output is correct
19 Correct 149 ms 35700 KB Output is correct
20 Correct 136 ms 35388 KB Output is correct
21 Correct 102 ms 35116 KB Output is correct
22 Correct 108 ms 35216 KB Output is correct
23 Correct 103 ms 35112 KB Output is correct