oj.uz

Submission #990059

# Submission time Handle Problem Language Result Execution time Memory
990059 2024-05-29T12:39:12 Z eyadooz Poklon (COCI17_poklon) C++14
0 / 140
 5000 ms 34964 KB 
// #include <iostream>
// #include <algorithm>
// #include <vector>
#include<bits/stdc++.h>
// #include <map>
// #include <set>
// #include <unordered_map>
// #include <unordered_set>
// #include <queue>
// #include <deque>
// #include <stack>
// #include <cmath>
// #include <math.h>
// #include <array>
// #include <random>
// #include <bitset>
// #include <climits>
// #include <cstring>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

// template <class x>
// using ordered_set = tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>;

typedef pair<int, int> ipair;

#define endl '\n'
#define mod 1000000007
#define INF 0x3f3f3f3f

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")

static inline int read()
{
    int x = 0;char ch = getchar();
    while (ch < '0' || ch>'9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}

static inline void print(const int &x) {
    if (x > 9)print(x / 10);
    putchar('0' + x % 10);
}

int di = 0;
unordered_map<int, int> asd;

bool cmp(array<int, 3> a, array<int, 3> b)
{
    if(a[0] / di < b[0] / di) return 1;
    else if(a[0] / di > b[0] / di) return 0;
    else
    {
        if(a[1] < b[1]) return 1;
        else if(a[1] > b[1]) return 0;
        else return 1;
    }
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n = read(), q = read();

    di = sqrt(n);

    int list[n];
    for(int i = 0;i < n;cin >> list[i++]);

    array<int, 3> qe[q];
    for(int i = 0;i < q;i++)
    {
        cin >> qe[i][0] >> qe[i][1];
        qe[i][0]--, qe[i][1]--;

        qe[i][2] = i;
    }

    sort(qe, qe + q,cmp);

    int cnt = 0;

    int ans[q], l = 0, r = -1;
    for(int i = 0;i < q;i++)
    {
        while(l < qe[i][0])
        {
            asd[list[l]]--;
            if(asd[list[l]] == 1) cnt--;
            else if(asd[list[l]] == 2) cnt++;
            l++;
        }
        while(l > qe[i][0])
        {
            l--;
            asd[list[l]]++;
            if(asd[list[l]] == 3) cnt--;
            else if(asd[list[l]] == 2) cnt++;
        }
        while(r < qe[i][1])
        {
            r++;
            asd[list[r]]++;
            if(asd[list[r]] == 3) cnt--;
            else if(asd[list[r]] == 2) cnt++;
        }
        while(r > qe[i][1])
        {
            asd[list[r]]--;
            if(asd[list[r]] == 1) cnt++;
            else if(asd[list[r]] == 0) cnt--;
            r--;
        }

        ans[qe[i][2]] = cnt;
    }

    for(int i = 0;i < q;i++) cout << ans[i] << endl;
    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 2000 KB Time limit exceeded
2 Execution timed out 5059 ms 4080 KB Time limit exceeded
3 Execution timed out 5069 ms 4248 KB Time limit exceeded
4 Execution timed out 5038 ms 3252 KB Time limit exceeded
5 Execution timed out 5019 ms 10168 KB Time limit exceeded
6 Runtime error 4225 ms 14536 KB Execution killed with signal 11
7 Execution timed out 5058 ms 16832 KB Time limit exceeded
8 Execution timed out 5074 ms 22040 KB Time limit exceeded
9 Execution timed out 5046 ms 29784 KB Time limit exceeded
10 Execution timed out 5063 ms 34964 KB Time limit exceeded