oj.uz

Submission #332442

# Submission time Handle Problem Language Result Execution time Memory
332442 2020-12-02T15:38:10 Z guka415 Poklon (COCI17_poklon) C++14
0 / 140
 1544 ms 22636 KB 
#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]]==1)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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 5 ms 620 KB Output isn't correct
5 Incorrect 167 ms 4460 KB Output isn't correct
6 Incorrect 168 ms 4588 KB Output isn't correct
7 Incorrect 438 ms 9068 KB Output isn't correct
8 Incorrect 767 ms 13720 KB Output isn't correct
9 Incorrect 1124 ms 18028 KB Output isn't correct
10 Incorrect 1544 ms 22636 KB Output isn't correct