oj.uz

Submission #990066

# Submission time Handle Problem Language Result Execution time Memory
990066 2024-05-29T12:46:27 Z eyadooz Poklon (COCI17_poklon) C++14
0 / 140
 5000 ms 39448 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#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>

using namespace std;

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")


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

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);
}


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]] == 2) 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 5050 ms 1876 KB Time limit exceeded
2 Execution timed out 5037 ms 4176 KB Time limit exceeded
3 Execution timed out 5032 ms 3864 KB Time limit exceeded
4 Execution timed out 5045 ms 4688 KB Time limit exceeded
5 Execution timed out 5077 ms 11716 KB Time limit exceeded
6 Execution timed out 5053 ms 11716 KB Time limit exceeded
7 Execution timed out 5033 ms 18812 KB Time limit exceeded
8 Execution timed out 5049 ms 24656 KB Time limit exceeded
9 Execution timed out 5021 ms 33520 KB Time limit exceeded
10 Execution timed out 5059 ms 39448 KB Time limit exceeded