Submission #332444

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332444	2020-12-02T15:42:36 Z	guka415	Poklon (COCI17_poklon)	C++14	140 / 140	1506 ms	13292 KB

poklon

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back

#include <iostream>
#include <algorithm>
#include <math.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<pii, int> query;

const int sz = 1e6;
int a[sz], cnts[sz];
int n, q;
int B;
query qu[sz];
int ans[sz];
unordered_map<int, int> inv;

void compress() {
    int cur=0;
    foru(i,0,n){
        if(inv.find(a[i])!=inv.end())a[i]=inv[a[i]];
        else {
            inv[a[i]]=cur++;
            a[i]=cur-1;
        }
    }
}


bool cmp(const query &l, const query &r) {
    if (l.first.first / B != r.first.first / B)return l.first.first < r.first.first;
    else if (l.first.second != r.first.second)return l.first.second < r.first.second;
    else if (l.first.first != r.first.first)return l.first.first < r.first.first;
    else return l.second < r.second;
}


int main() {
    fast;
    cin >> n>>q;
    foru(i, 0, n)cin >> a[i];
    foru(i, 0, q) {
        cin >> qu[i].first.first >> qu[i].first.second;
        qu[i].first.first--;
        qu[i].first.second--;
        qu[i].second = i;
    }
    compress();
    B = (int)((ld)n / sqrtl(q));
    sort(qu, qu + q, cmp);
    int prv = -1, l = -1,r=-1,ret=0;
    foru(i,0,q){
        int block = qu[i].first.first/B;
        if(block!=prv){
            ret=0;
            foru(j,0,n)cnts[j]=0;
            l=qu[i].first.first,r=qu[i].first.second;
            foru(j,l,r+1){
                cnts[a[j]]++;
                if(cnts[a[j]]==2)ret++;
                if(cnts[a[j]]==3)ret--;
            }
        }
        else {
            while(l>qu[i].first.first){
                cnts[a[--l]]++;
                if(cnts[a[l]]==2)ret++;
                if(cnts[a[l]]==3)ret--;
            }
            while(l<qu[i].first.first){
                cnts[a[l++]]--;
                if(cnts[a[l-1]]==1)ret--;
                if(cnts[a[l-1]]==2)ret++;
            }
            while(r<qu[i].first.second){
                cnts[a[++r]]++;
                if(cnts[a[r]]==2)ret++;
                if(cnts[a[r]]==3)ret--;
            }
        }
        ans[qu[i].second]=ret;
        prv=block;
    }
    foru(i,0,q)cout<<ans[i]<<'\n';
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	5 ms	492 KB	Output is correct
5	Correct	166 ms	2924 KB	Output is correct
6	Correct	165 ms	2924 KB	Output is correct
7	Correct	455 ms	5612 KB	Output is correct
8	Correct	751 ms	8172 KB	Output is correct
9	Correct	1121 ms	10816 KB	Output is correct
10	Correct	1506 ms	13292 KB	Output is correct