# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62653 | 2018-07-29T16:17:03 Z | win11905 | Poklon (COCI17_poklon) | C++11 | 5000 ms | 40132 KB |
#include <bits/stdc++.h> using namespace std; #define iii tuple<int, int, int> #define pii pair<int, int> #define x first #define y second const int N = 5e5+5; const int sz = 708; int n, m, A[N], ans[N]; vector<iii> block[sz]; int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%d", A+i); for(int i = 0, a, b; i < m; ++i) { scanf("%d %d", &a, &b); block[a/sz].emplace_back(a, b, i); } for(int i = 0; i < sz; ++i) { sort(block[i].begin(), block[i].end(), [&](const iii &a, const iii &b) { return get<1>(a) < get<1>(b); }); int l = i * sz, r = i * sz; map<int, int> M; int cnt = 0; auto add = [&](int v) { if(M[v] == 2) cnt--; if(M[v] == 1) cnt++; M[v]++; }; auto del = [&](int v) { if(M[v] == 3) cnt++; if(M[v] == 2) cnt--; M[v]--; }; for(iii z : block[i]) { int p, x, y; tie(x, y, p) = z; while(r <= y) add(A[r++]); while(l < x) del(A[l++]); while(l > x) add(A[--l]); ans[p] = cnt; } } for_each(ans, ans+m, [](int x) { printf("%d\n", x); }); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 376 KB | Output is correct |
2 | Correct | 6 ms | 492 KB | Output is correct |
3 | Correct | 23 ms | 612 KB | Output is correct |
4 | Correct | 90 ms | 848 KB | Output is correct |
5 | Correct | 2744 ms | 4820 KB | Output is correct |
6 | Correct | 3914 ms | 6368 KB | Output is correct |
7 | Execution timed out | 5076 ms | 12064 KB | Time limit exceeded |
8 | Execution timed out | 5096 ms | 19676 KB | Time limit exceeded |
9 | Execution timed out | 5068 ms | 29048 KB | Time limit exceeded |
10 | Execution timed out | 5036 ms | 40132 KB | Time limit exceeded |