제출 #563028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563028		ddy888	Poklon (COCI17_poklon)	C++17	140 / 140	1812 ms	23080 KiB

poklon

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 500010, BLK = 700;
struct Query {
    int idx, l, r;
    bool operator<(const Query&o) const {
        return pi(l / BLK, r) < pi(o.l / BLK, o.r);
    };
};

int n, q;
int a[MAXN], ans[MAXN], active[MAXN], in[MAXN];
vector<Query> qq;
vi vals;
int cur;

void add(int id) {
    ++active[id];
    if (active[id] == 2) {
        ++cur;
        in[id] = 1;
    } else if (active[id] > 2) {
        cur -= in[id];
        in[id] = 0;
    }
}

void remove(int id) {
    --active[id];
    if (active[id] == 2) {
        ++cur;
        in[id] = 1;
    } else if (active[id] < 2) {
        cur -= in[id];
        in[id] = 0;
    }
}

int main() {
    fast;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];   
        vals.pb(a[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
    for (int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        qq.pb({i, l, r});
    }
    sort(qq.begin(), qq.end());
    int lc = 0, rc = 0;
    for (auto i: qq) {
        while (lc > i.l) {
            --lc;
            add(a[lc]);
        }
        while (rc < i.r) {
            ++rc;
            add(a[rc]);
        }
        while (lc < i.l) {
            remove(a[lc]);
            ++lc;
        }
        while (rc > i.r) {
            remove(a[rc]);
            --rc;
        }
        ans[i.idx] = cur;
    }
    for (int i = 1; i <= q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

• Subtask 1: 140 / 140