oj.uz

Submission #818867

# Submission time Handle Problem Language Result Execution time Memory
818867 2023-08-10T07:06:24 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 463 ms 36624 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define TASK ""
#define BIT(x, i) (x & (1 << i))
#define MASK(x) (1 << (x))
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int maxn = 5e5 + 3;
int n, maxx, pre[maxn], idx[maxn], seg[maxn << 1], a[maxn];
vector <int> b;
vector<pair<int,int>>queries[maxn];
int ans[maxn];
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;
}

void update(int p, int val){
    seg[p += n] += val;
    for(p >>= 1; p; p >>= 1)
        seg[p] = seg[p << 1] + seg[p << 1 | 1];
}

int get(int l, int r){
    int sum = 0;
    for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1){
        if (l & 1)
            sum += seg[l++];
        if (r & 1)
            sum += seg[--r];
    }
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);
    int q, l, r;
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        b.pb(a[i]);
    }
    sort(all(b));

   for (int i = 1; i <= q; i++){
        int l,r;
        cin >> l >> r;
        queries[r].pb(make_pair(l,i));
    }
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(all(b),a[i]) - b.begin() + 1;
        //idx[i] = pre[a[i]];
        idx[i] = pre[p];
        pre[p] = i;
    }
    for (int r = 1;r <= n; r++) {
        int i = idx[r];
        int j = idx[i];
        int z = idx[j];
        if(i) update(i,1);
        if(j) update(j,-2);
        if(z) update(z,1);
        for (auto it : queries[r]) ans[it.se] = get(it.fi,r);
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
    return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:53:12: warning: unused variable 'l' [-Wunused-variable]
   53 |     int q, l, r;
      |            ^
poklon.cpp:53:15: warning: unused variable 'r' [-Wunused-variable]
   53 |     int q, l, r;
      |               ^

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 6 ms 12076 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 8 ms 12356 KB Output is correct
5 Correct 67 ms 16804 KB Output is correct
6 Correct 71 ms 16984 KB Output is correct
7 Correct 167 ms 21828 KB Output is correct
8 Correct 269 ms 26880 KB Output is correct
9 Correct 405 ms 31684 KB Output is correct
10 Correct 463 ms 36624 KB Output is correct