Submission #62653

# Submission time Handle Problem Language Result Execution time Memory
62653 2018-07-29T16:17:03 Z win11905 Poklon (COCI17_poklon) C++11
84 / 140
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

poklon.cpp: In function 'int main()':
poklon.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:17:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~
poklon.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
# 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