oj.uz

Submission #246066

# Submission time Handle Problem Language Result Execution time Memory
246066 2020-07-08T06:39:54 Z VEGAnn Poklon (COCI17_poklon) C++14
28 / 140
 5000 ms 33128 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;

    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 2102 ms 12696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Execution timed out 5060 ms 8948 KB Time limit exceeded
6 Runtime error 2204 ms 13424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Execution timed out 5086 ms 12144 KB Time limit exceeded
8 Runtime error 628 ms 23284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2259 ms 29008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 865 ms 33128 KB Execution killed with signal 11 (could be triggered by violating memory limits)