Submission #990053

#	Time	Username	Problem	Language	Result	Execution time	Memory
990053		eyadooz	Poklon (COCI17_poklon)	C++14	84 / 140	5072 ms	10068 KiB

poklon

#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, q;

    cin >> n >> q;

    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(auto i : ans) cout << i << "\n";
    return 0;
}

• Subtask 1: 84 / 140