oj.uz

Submission #246073

# Submission time Handle Problem Language Result Execution time Memory
246073 2020-07-08T06:51:09 Z VEGAnn Poklon (COCI17_poklon) C++14
0 / 140
 5000 ms 24932 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;

    while (1) {}

    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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 384 KB Time limit exceeded
2 Execution timed out 5048 ms 384 KB Time limit exceeded
3 Runtime error 11 ms 4608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2171 ms 12664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Execution timed out 5048 ms 7944 KB Time limit exceeded
6 Runtime error 2154 ms 12320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Execution timed out 5059 ms 9196 KB Time limit exceeded
8 Runtime error 625 ms 18536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2359 ms 22724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 832 ms 24932 KB Execution killed with signal 11 (could be triggered by violating memory limits)