Submission #1227859

#TimeUsernameProblemLanguageResultExecution timeMemory
1227859salmonRailway Trip (JOI17_railway_trip)C++20
100 / 100
198 ms38556 KiB
#include <bits/stdc++.h> using namespace std; int N,Q; int lst[200100]; vector<int> pos[200100]; int l[25][200100]; int r[25][200100]; map<pair<int,int>,int> mep; int direc[200100][2]; struct node{ int s, e, m; int v; node *l, *r; node(int S, int E){ s = S; e = E; m = (s + e)/2; if(s != e){ l = new node(s,m); r = new node(m + 1, e); v = max(l -> v, r -> v); } else{ v = lst[s]; } } int query(int S, int E){ if(S <= s && e <= E) return v; int V = 0; if(S <= m) V = max(V, l -> query(S,E)); if(m < E) V = max(V, r -> query(S,E)) ; return V; } }*root; int main(){ int K; scanf(" %d",&N); scanf(" %d",&K); scanf(" %d",&Q); for(int i = 1; i <= N; i++){ scanf(" %d",&lst[i]); if(i != 1 && i != N) pos[lst[i]].push_back(i); } vector<int> steck = {1}; direc[1][0] = -1; for(int i = 2; i <= N; i++){ while(lst[steck.back()] < lst[i]) steck.pop_back(); direc[i][0] = steck.back(); steck.push_back(i); } direc[N][1] = -1; steck = {N}; for(int i = N - 1; i >= 1; i--){ while(lst[steck.back()] < lst[i]) steck.pop_back(); direc[i][1] = steck.back(); steck.push_back(i); } root = new node(1,N); for(int i = 1; i <= N; i++){ l[0][i] = max(1,direc[i][0]); r[0][i] = min(N,direc[i][1]); } r[0][N] = N; for(int j = 1; j < 25; j++){ for(int i = 1; i <= N; i++){ l[j][i] = min(l[j - 1][l[j - 1][i]], l[j - 1][r[j - 1][i]]); r[j][i] = max(r[j - 1][l[j - 1][i]], r[j - 1][r[j - 1][i]]); } } for(int i = 0; i < Q; i++){ int A, B; scanf(" %d",&A); scanf(" %d",&B); int num = 0; int l1, r1; l1 = A; r1 = A; for(int j = 24; j >= 0; j--){ if(max(r[j][l1], r[j][r1]) < B || B < min(l[j][l1], l[j][r1])){ int temp = min(l[j][l1], l[j][r1]); r1 = max(r[j][l1], r[j][r1]); l1 = temp; num += (1<<j); } } int l2,r2; l2 = B; r2 = B; for(int j = 24; j >= 0; j--){ if(max(r[j][l2], r[j][r2]) < l1 || r1 < min(l[j][l2], l[j][r2])){ int temp = min(l[j][l2], l[j][r2]); r2 = max(r[j][l2], r[j][r2]); l2 = temp; num += (1<<j); } } printf("%d\n",num + 1 - 1); } }

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 scanf(" %d",&A);
      |                 ~~~~~^~~~~~~~~~
railway_trip.cpp:102:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 scanf(" %d",&B);
      |                 ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...