oj.uz

답안 #941320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941320 2024-03-08T13:34:05 Z phamducminh Poklon (COCI17_poklon) C++17
0 / 140
 4754 ms 14116 KB 


#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Incorrect 3 ms 4444 KB Output isn't correct
4 Incorrect 13 ms 4684 KB Output isn't correct
5 Incorrect 402 ms 7648 KB Output isn't correct
6 Incorrect 391 ms 7560 KB Output isn't correct
7 Incorrect 1065 ms 10752 KB Output isn't correct
8 Incorrect 2057 ms 12020 KB Output isn't correct
9 Incorrect 3178 ms 13088 KB Output isn't correct
10 Incorrect 4754 ms 14116 KB Output isn't correct