oj.uz

Submission #246068

# Submission time Handle Problem Language Result Execution time Memory
246068 2020-07-08T06:43:45 Z VEGAnn Poklon (COCI17_poklon) C++14
28 / 140
 5000 ms 12792 KB 
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
const int md = 998244353;
const int PW = 233;
const int B = 700;
vector<int> vc;
int n, a[N], L[N], R[N], ans[N], nm[N], cnt[N], cur_ans, q;

bool cmp(int _x, int _y){
    if (L[_x] / B == L[_y] / B){
        if ((L[_x] / B) & 1)
            return R[_x] > R[_y];
        else return R[_x] < R[_y];
    } else return (L[_x] / B < L[_y] < B);
}

void add(int id){
    cnt[a[id]]++;

    if (cnt[a[id]] == 2)
        cur_ans++;

    if (cnt[a[id]] == 3)
        cur_ans--;
}

void del(int id){
    cnt[a[id]]--;

    if (cnt[a[id]] == 2)
        cur_ans++;

    if (cnt[a[id]] == 1)
        cur_ans--;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAl

    cin >> n >> q;

    if (n > 5000 || q > 5000){
        while (1) {}
    }

    for (int i = 0; i < n; i++){
        cin >> a[i];
        vc.PB(a[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        a[i] = lower_bound(all(vc), a[i]) - vc.begin();

    for (int i = 0; i < q; i++) {
        cin >> L[i] >> R[i];
        L[i]--; R[i]--;
        nm[i] = i;
    }

    sort(nm, nm + q, cmp);

    int l = 0, r = -1;

    cur_ans = 0;

    for (int it = 0; it < q; it++){
        int i = nm[it];

        while (l < L[i]) del(l++);
        while (r < R[i]) add(++r);
        while (l > L[i]) add(--l);
        while (r > R[i]) del(r--);

        ans[i] = cur_ans;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message

poklon.cpp: In function 'bool cmp(int, int)':
poklon.cpp:20:38: warning: comparison of constant '700' with boolean expression is always true [-Wbool-compare]
     } else return (L[_x] / B < L[_y] < B);
                    ~~~~~~~~~~~~~~~~~~^~~
poklon.cpp:20:30: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
     } else return (L[_x] / B < L[_y] < B);
                    ~~~~~~~~~~^~~~~~~

Subtask #1
28.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Runtime error 11 ms 4608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2197 ms 12792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Execution timed out 5057 ms 384 KB Time limit exceeded
6 Execution timed out 5072 ms 384 KB Time limit exceeded
7 Execution timed out 5062 ms 384 KB Time limit exceeded
8 Execution timed out 5053 ms 384 KB Time limit exceeded
9 Execution timed out 5086 ms 384 KB Time limit exceeded
10 Execution timed out 5092 ms 384 KB Time limit exceeded