oj.uz

Submission #818084

# Submission time Handle Problem Language Result Execution time Memory
818084 2023-08-10T01:51:54 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 316 ms 32760 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 5e5 + 7;
const ll oo = 1e18 + 69;

int n, q, a[maxn], l, r, mp[maxn], near[maxn], res[maxn];
vector<pa> events[maxn];

struct BIT {
    int bit[maxn];

    void update(int x, int val) {
        for(; x <= n; x += x&-x) bit[x] += val;
    }

    int get(int x) {
        int ans = 0;
        for(; x; x-= x&-x) ans += bit[x];
        return ans;
    }

    int query(int l, int r) {
        return get(r) - get(l - 1);
    }
} bit;

void add(int i, int val) {
    if(near[i] != 0) {
        bit.update(near[i], val);
        if(near[near[i]] != 0) {
            bit.update(near[near[i]], -val);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q;
    vector<int> val;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
        val.pb(a[i]);
    }

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

    for(int i = 0; i < q; i++) {
        cin>>l>>r;
        events[r].pb({l, i});
    }

    for(int i = 1; i <= n; i++) {
        if(mp[a[i]]) add(mp[a[i]], -1);
        near[i] = mp[a[i]];
        mp[a[i]] = i;
        add(i, 1);

        for(auto e:events[i]) {
            res[e.se] = bit.query(e.fi, i);
        }
    }

    for(int i = 0; i < q; i++) cout<<res[i]<<"\n";
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 5 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 54 ms 16172 KB Output is correct
6 Correct 51 ms 16208 KB Output is correct
7 Correct 113 ms 20316 KB Output is correct
8 Correct 172 ms 24532 KB Output is correct
9 Correct 253 ms 28672 KB Output is correct
10 Correct 316 ms 32760 KB Output is correct