Submission #1188749

#TimeUsernameProblemLanguageResultExecution timeMemory
1188749_dtq_Poklon (COCI17_poklon)C++17
0 / 140
931 ms44168 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(v) v.begin(), v.end() #define sz(x) (long long)(x.size()) using namespace std; const ll N = 5e5 + 9; ll n, i, q, l, r, a[N], ans[N], dem[N]; vector<ll>vec; void calc( ll l, ll r ) { for( int w = l; w <= r; w ++ ) dem[a[w]] ++; for( int w = l; w <= r; w ++ ) { ans[i] += (dem[a[w]] == 2); dem[a[w]] = 0; } } struct abc{ ll l, r, id; }; vector<abc>save[N]; bool cmp( abc x, abc y ) { return x.r < y.r; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> q; for( i = 1; i <= n; i ++ ) cin >> a[i], vec.pb(a[i]); sort(all(vec)); for( i = 1; i <= n; i ++ ) a[i] = lower_bound(all(vec), a[i]) - vec.begin(); ll c = sqrt(n); if(c * c != n) c ++; for( i = 1; i <= q; i ++ ) { cin >> l >> r; if(r - l + 1 <= c) { calc(l, r); continue; } ll block = l / c + (l % c != 0); save[block].pb({l, r, i}); } for( i = 1; i <= c + 2; i ++ ) sort(all(save[i]), cmp); for( i = 1; i <= c + 2; i ++ ) { if(sz(save[i]) == 0) continue; ll x = (i - 1) * c + 1, y = min(n, i * c); ll cnt = 0; ll vt = y + 1; for(auto k : save[i]) { ll l = k.l, r = k.r; for( int w = l; w <= y; w ++ ) { dem[a[w]] ++; cnt += (dem[a[w]] == 2); cnt -= (dem[a[w]] == 3); } while(vt <= r) { dem[a[vt]] ++; cnt += (dem[a[vt]] == 2); cnt -= (dem[a[vt]] == 3); vt ++; } ans[k.id] = cnt; for( int w = l; w <= y; w ++ ) { dem[a[w]] --; cnt += (dem[a[w]] == 2); cnt -= (dem[a[w]] == 1); } } } for( i = 1; i <= q; i ++ ) cout << ans[i] << "\n"; return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...