Submission #862476

#TimeUsernameProblemLanguageResultExecution timeMemory
862476HossamHero7Osumnjičeni (COCI21_osumnjiceni)C++14
0 / 110
262 ms20640 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' void compress(vector<int> &a){ int n = a.size(); vector<pair<int,int>> b(n); for(int i=0;i<n;i++){ b[i].first = a[i]; b[i].second = i; } sort(b.begin(),b.end()); a[b[0].second] = 1; int cnt = 1; for(int i=1;i<n;i++){ if(b[i].first == b[i-1].first){ a[b[i].second] = a[b[i-1].second]; } else a[b[i].second] = ++cnt; } } struct segTree{ int n; vector<int> tree; vector<int> lazy; segTree(int _n){ n = _n; tree.resize(4*n+5,-1); lazy.resize(4*n+5,-1); } void prop(int node,int l,int r){ tree[node] = lazy[node]; if(l != r){ lazy[node<<1] = lazy[node]; lazy[node<<1|1] = lazy[node]; } lazy[node] = -1; } void update(int node,int l,int r,int lQ,int rQ,int val){ if(l>r) return; if(~lazy[node]) prop(node,l,r); if(lQ>r || l>rQ) return; if(lQ<=l&&r<=rQ) return lazy[node] = val, prop(node,l,r), void(); int md = l + r >> 1; update(node<<1,l,md,lQ,rQ,val), update(node<<1|1,md+1,r,lQ,rQ,val); tree[node] = max(tree[node<<1] , tree[node<<1|1]); } void update(int l,int r,int val){ update(1,1,n,l,r,val); } int query(int node,int l,int r,int lQ,int rQ){ if(l>r) return -1; if(~lazy[node]) prop(node,l,r); if(lQ>r || l>rQ) return -1; if(lQ<=l&&r<=rQ) return tree[node]; int md = l + r >> 1; return max(query(node<<1,l,md,lQ,rQ) , query(node<<1|1,md+1,r,lQ,rQ)); } int query(int l,int r){ return query(1,1,n,l,r); } }; void solve(){ int n; cin>>n; vector<pair<int,int>> v(n); for(auto &[l,r] : v) cin>>l>>r; vector<int> tmp; for(auto [l,r] : v) tmp.push_back(l); for(auto [l,r] : v) tmp.push_back(r); compress(tmp); for(int i=0;i<n;i++) v[i] = {tmp[i],tmp[i+n]}; segTree sg(n*2); vector<int> lst(n); for(int i=0;i<n;i++){ int l = v[i].first , r = v[i].second; lst[i] = sg.query(l,r); sg.update(l,r,i); } int q; cin>>q; while(q--){ int a,b; cin>>a>>b; a --, b --; int st = a; int ans = 1; for(int i=a;i<=b;i++){ if(lst[i] >= st) { ans ++; st = lst[i]; } } cout<<ans<<endl; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

Main.cpp: In member function 'void segTree::update(int, int, int, int, int, int)':
Main.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:56:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto &[l,r] : v) cin>>l>>r;
      |               ^
Main.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [l,r] : v) tmp.push_back(l);
      |              ^
Main.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto [l,r] : v) tmp.push_back(r);
      |              ^
#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...