oj.uz

Submission #62655

# Submission time Handle Problem Language Result Execution time Memory
62655 2018-07-29T16:33:08 Z win11905 Poklon (COCI17_poklon) C++11
0 / 140
 1029 ms 30668 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);
            M[A[i]].pop_front();
        }
        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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 12280 KB Output isn't correct
2 Incorrect 18 ms 12280 KB Output isn't correct
3 Incorrect 17 ms 12472 KB Output isn't correct
4 Incorrect 23 ms 12472 KB Output isn't correct
5 Incorrect 175 ms 15788 KB Output isn't correct
6 Incorrect 140 ms 15928 KB Output isn't correct
7 Incorrect 327 ms 19812 KB Output isn't correct
8 Incorrect 569 ms 24228 KB Output isn't correct
9 Incorrect 812 ms 27228 KB Output isn't correct
10 Incorrect 1029 ms 30668 KB Output isn't correct