Submission #675794

#TimeUsernameProblemLanguageResultExecution timeMemory
675794VictorOsumnjičeni (COCI21_osumnjiceni)C++17
60 / 110
1117 ms409556 KiB
//#pragma GCC target ("avx,avx2,fma") //#pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast //#pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb push_back #define debug(x) cout<<#x<<" = "<<x<<endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; const int inf = 1e9; struct Node { Node *l = 0, *r = 0; int lo, hi, mset = inf, val = inf; Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of -inf Node(vi& v, int lo, int hi) : lo(lo), hi(hi) { if (lo + 1 < hi) { int mid = lo + (hi - lo)/2; l = new Node(v, lo, mid); r = new Node(v, mid, hi); val = min(l->val, r->val); } else val = v[lo]; } int query(int L, int R) { if (R <= lo || hi <= L) return inf; if (L <= lo && hi <= R) return val; push(); return min(l->query(L, R), r->query(L, R)); } void set(int L, int R, int x) { if (R <= lo || hi <= L) return; if (L <= lo && hi <= R) mset = val = x; else { push(), l->set(L, R, x), r->set(L, R, x); val = min(l->val, r->val); } } void push() { if (!l) { int mid = lo + (hi - lo)/2; l = new Node(lo, mid); r = new Node(mid, hi); } if (mset != inf) l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf; } }; int jmp[18][200005]; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int n,q; int heights[200005][2]; cin>>n; //set<int> unique_heights; rep(i,0,n) rep(j,0,2) cin>>heights[i][j];//,unique_heights.insert(heights[i][j]); //umap<int,int> compress; //int cnt=0; //trav(height,unique_heights) compress[height]=cnt++; //rep(i,0,n) rep(j,0,2) heights[i][j]=compress[heights[i][j]]; Node segtree(0,INF); int min_val=n; per(i,0,n) { jmp[0][i]=segtree.query(heights[i][0],heights[i][1]+1); if(i+1!=n) jmp[0][i]=min(jmp[0][i],jmp[0][i+1]); //debug(jmp[0][i])<<endl; segtree.set(heights[i][0],heights[i][1]+1,i); } rep(j,1,18) rep(i,0,n) { if(jmp[j-1][i]>=inf) jmp[j][i]=inf; else jmp[j][i]=jmp[j-1][jmp[j-1][i]]; } cin>>q; while(q--) { int lo,hi; cin>>lo>>hi; --lo; int cnt=1; //cout<<"lo = "<<lo<<" hi = "<<hi<<endl; per(j,0,18) { //cout<<"j = "<<j<<" lo = "<<lo<<" jmp = "<<jmp[j][lo]<<endl; if(jmp[j][lo]<hi) { cnt+=1<<j; lo=jmp[j][lo]; } } cout<<cnt<<endl; } _Exit(0); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:90:6: warning: unused variable 'min_val' [-Wunused-variable]
   90 |  int min_val=n;
      |      ^~~~~~~
#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...