oj.uz

Submission #62656

# Submission time Handle Problem Language Result Execution time Memory
62656 2018-07-29T16:34:11 Z win11905 Poklon (COCI17_poklon) C++11
140 / 140
 1006 ms 29656 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define x first
#define y second

const int N = 5e5+5;

int n, m, A[N], t[N], ans[N];
vector<pii> que[N];

void update(int x, int v) {
    for(; x; x -= x & -x) t[x] += v;
}

int query(int x) {
    int sum = 0;
    for(; x <= n; x += x & -x) sum += t[x];
    return sum;
}

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);
        que[b].emplace_back(a, i);
    }
    map<int, deque<int> > M;
    for(int i = 1; i <= n; ++i) {
        if(M[A[i]].empty()) M[A[i]].push_back(0);
        if(M[A[i]].size() == 3) {
            update(M[A[i]][0], 1), update(M[A[i]][1], -1);
            M[A[i]].pop_front();
        }
        M[A[i]].push_back(i);
        if(M[A[i]].size() == 3) 
            update(M[A[i]][0], -1), update(M[A[i]][1], 1);
        for(pii z : que[i]) ans[z.y] = query(z.x);
    }
    for_each(ans, ans+m, [](int x) { printf("%d\n", x); });
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:24: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:25: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:27: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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12132 KB Output is correct
2 Correct 13 ms 12136 KB Output is correct
3 Correct 17 ms 12340 KB Output is correct
4 Correct 21 ms 12416 KB Output is correct
5 Correct 158 ms 15744 KB Output is correct
6 Correct 179 ms 15744 KB Output is correct
7 Correct 431 ms 19348 KB Output is correct
8 Correct 706 ms 23184 KB Output is correct
9 Correct 965 ms 26348 KB Output is correct
10 Correct 1006 ms 29656 KB Output is correct