Submission #941320

#	Time	Username	Problem	Language	Result	Execution time	Memory
941320		phamducminh	Poklon (COCI17_poklon)	C++17	0 / 140	4754 ms	14116 KiB

poklon

#include <bits/stdc++.h>

using namespace std;


#define all(a)      a.begin(),a.end()


const long long maxN = 5e5+12;








///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);










    long long t;


    // cin >> t; 

    t=1;



    while (t--){




        solve();


    }






    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///




int a[maxN],cur=0,n,q,ans[maxN],block;
vector<int> b;
unordered_map<int,int> mm;
int _left, _right;

struct Query {
    int l, r, pos;
};

Query queries[maxN];

int lg=700;

bool cmp(Query x, Query y) {
    return (make_pair(x.l / lg, x.r) < make_pair(y.l / lg, y.r));
}



void add(int pos) {
    if (pos==0) return;
    mm[a[pos]]++;
    if (mm[a[pos]] == 1) {
        cur++;
    }
}

void erase(int pos) {
    if (pos==0) return;
    mm[a[pos]]--;
    if (mm[a[pos]] == 0) {
        cur--;
    }
}



void mo(int i){

    int left = queries[i].l, right = queries[i].r;

    while (_left<left){
        erase(_left);
        _left++;
    }
    while (_left>left){
        add(_left-1);
        _left--;
    }
    while (_right>right){
        erase(_right);
        _right--;
    }
    while (_right<right){
        add(_right+1);
        _right++;
    } 
}



void solve(){


    cin >> n >> q;

    // block=(int)sqrt(n);

    for (int i=1; i<=n; i++){
        cin >> a[i];
        b.push_back(a[i]);
    }

    sort(all(b));
    b.resize(unique(all(b)) - b.begin());
 
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(all(b), a[i]) - b.begin() + 1;

    for (int i=1; i<=q; i++){
        cin >> queries[i].l >> queries[i].r;

        queries[i].pos=i;
    }


    sort(queries+1,queries+q+1,cmp);


    for (int i=1; i<=q; i++){

        mo(i);
        ans[queries[i].pos]=cur;
    }


    for (int i=1; i<=q; i++){
        cout << ans[i] << "\n";
    }




}

• Subtask 1: 0 / 140