oj.uz

Submission #380629

# Submission time Handle Problem Language Result Execution time Memory
380629 2021-03-22T15:40:24 Z BeanZ Poklon (COCI17_poklon) C++14
140 / 140
 1800 ms 33628 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 5e5 + 5;
long long mod = 1e9 + 7;
const int lim = 2e5;
const int lg = 19;
const int base = 700;
const long double eps = 1e-6;
struct viet{
    ll l, r, id;
    bool operator <(const viet &o){
        if ((l / base) == (o.l / base)) return r < o.r;
        return (l / base) < (o.l / base);
    }
};
ll cnt[N], a[N], ans[N];
ll now = 0;
void add(ll u){
    if (cnt[a[u]] == 1) now++;
    if (cnt[a[u]] == 2) now--;
    cnt[a[u]]++;
}
void del(ll u){
    if (cnt[a[u]] == 3) now++;
    if (cnt[a[u]] == 2) now--;
    cnt[a[u]]--;
}
viet Q[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("tests.inp", "r", stdin);
        freopen("tests.out", "w", stdout);
    }
    ll n, q;
    cin >> n >> q;
    vector<ll> val;
    for (int i = 1; i <= n; i++) cin >> a[i], val.push_back(a[i]);
    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
    }
    for (int i = 1; i <= q; i++){
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }
    sort(Q + 1, Q + q + 1);
    ll l = 1, r = 0;
    for (int i = 1; i <= q; i++){
        while (r > Q[i].r){
            del(r);
            r--;
        }
        while (l < Q[i].l){
            del(l);
            l++;
        }
        while (r < Q[i].r){
            r++;
            add(r);
        }
        while (l > Q[i].l){
            l--;
            add(l);
        }
        ans[Q[i].id] = now;
    }
    for (int i = 1; i <= q; i++){
        cout << ans[i] << endl;
    }
}
/*
Ans:

Out:
*/

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 |         freopen("tests.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   37 |         freopen("tests.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 169 ms 6888 KB Output is correct
6 Correct 176 ms 6936 KB Output is correct
7 Correct 452 ms 13688 KB Output is correct
8 Correct 841 ms 20360 KB Output is correct
9 Correct 1275 ms 26956 KB Output is correct
10 Correct 1800 ms 33628 KB Output is correct