제출 #990067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990067		eyadooz	Poklon (COCI17_poklon)	C++14	0 / 140	5092 ms	34984 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>

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++) print(ans[i]);
    return 0;
}

• Subtask 1: 0 / 140