Submission #672501

#TimeUsernameProblemLanguageResultExecution timeMemory
672501tamthegodPoklon (COCI17_poklon)C++14
140 / 140
1000 ms62668 KiB
// Make the best become better // No room for laziness #include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, q; int a[maxN]; int st[4 * maxN]; vector<pair<int, int>> qu[maxN]; int res[maxN]; void update(int id, int l, int r, int pos, int val) { if(l > pos || r < pos) return; if(l == r && l == pos) { st[id] = val; return; } int mid = (l + r) / 2; update(id * 2, l, mid, pos, val); update(id * 2 + 1, mid + 1, r, pos, val); st[id] = st[id * 2] + st[id * 2 + 1]; } int get(int id, int l, int r, int u, int v) { if(l > v || r < u) return 0; if(l >= u && r <= v) return st[id]; int mid = (l + r) / 2; return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); } void ReadInput() { cin >> n >> q; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=q; i++) { int l, r; cin >> l >> r; qu[r].pb({l, i}); } } void Solve() { map<int, int> last[3]; for(int i=1; i<=n; i++) { if(last[0][a[i]]) update(1, 1, n, last[0][a[i]], 1); if(last[1][a[i]]) update(1, 1, n, last[1][a[i]], -1); if(last[2][a[i]]) update(1, 1, n, last[2][a[i]], 0); last[2][a[i]] = last[1][a[i]]; last[1][a[i]] = last[0][a[i]]; last[0][a[i]] = i; for(auto v : qu[i]) res[v.se] = get(1, 1, n, v.fi, i); } for(int i=1; i<=q; i++) cout << res[i] << '\n'; } int32_t main() { //freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...