oj.uz

Submission #563028

# Submission time Handle Problem Language Result Execution time Memory
563028 2022-05-16T05:43:10 Z ddy888 Poklon (COCI17_poklon) C++17
140 / 140
 1812 ms 23080 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 168 ms 4656 KB Output is correct
6 Correct 174 ms 4656 KB Output is correct
7 Correct 444 ms 9488 KB Output is correct
8 Correct 846 ms 15096 KB Output is correct
9 Correct 1284 ms 18924 KB Output is correct
10 Correct 1812 ms 23080 KB Output is correct