Submission #62653

#	Time	Username	Problem	Language	Result	Execution time	Memory
62653		win11905	Poklon (COCI17_poklon)	C++11	84 / 140	5096 ms	40132 KiB

poklon

#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 (stderr)

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);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 84 / 140