oj.uz

Submission #990056

# Submission time Handle Problem Language Result Execution time Memory
990056 2024-05-29T12:35:36 Z eyadooz Poklon (COCI17_poklon) C++14
0 / 140
 5000 ms 34384 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>
// #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;
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]] == 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 5038 ms 2204 KB Time limit exceeded
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Execution timed out 5086 ms 2320 KB Time limit exceeded
4 Execution timed out 5057 ms 2064 KB Time limit exceeded
5 Execution timed out 5021 ms 7900 KB Time limit exceeded
6 Execution timed out 5051 ms 8788 KB Time limit exceeded
7 Execution timed out 5068 ms 16308 KB Time limit exceeded
8 Execution timed out 5049 ms 21000 KB Time limit exceeded
9 Execution timed out 5022 ms 27688 KB Time limit exceeded
10 Execution timed out 5077 ms 34384 KB Time limit exceeded