oj.uz

Submission #818224

# Submission time Handle Problem Language Result Execution time Memory
818224 2023-08-10T04:06:56 Z vjudge1 Poklon (COCI17_poklon) C++17
0 / 140
 5000 ms 13252 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define endl "\n"
#define bit(x) (1<<x);
#define getbit(x,pos) ((x<<pos)&1)
#define all(x) x.begin(),x.end()

using namespace std;

template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

const int N=2e5+7;
//const long long p=1e9+7;
const int base=31;
const long long oo =1e18;

typedef pair<int,int> ii;
typedef vector<ii> vii;
int n;
int q;
int a[N];
int s[N];
int idx[N];
int pre[N];
int ans[N];
vector<int>v;
vector<pair<int,int>>queries[N];

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v.pb(a[i]);
    }
    sort(all(v));
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(all(v),a[i]) - v.begin() + 1;
        idx[i] = pre[p];
        pre[p] = i;
    }
    for (int i = 1; i <= q;i++) {
        int u,v;
        cin >> u >> v;
        queries[v].pb(make_pair(u,i));
    }
    for (int r = 1; r <= n; r++) {
        int j = idx[r];
        int i = idx[j];
        int z = idx[i];
        if(j > 0) s[j]++;
        if(i > 0) s[i] -= 2;
        if(z > 0) s[z] ++;
        if((int)queries[r].size() == 0) continue;
        for (int i = 1; i <= r; i++) s[i] = s[i - 1] + s[i];
        for (auto it : queries[r]) {
            int l = it.fi;
            int id = it.se;
            ans[id] = s[r] - s[l - 1];
        }
    }
    for (int i = 1; i <= q; i++) cout << (ans[i] > 0 ? ans[i] : 0) << " ";
    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Incorrect 2 ms 5076 KB Output isn't correct
3 Incorrect 3 ms 5076 KB Output isn't correct
4 Incorrect 22 ms 5260 KB Output isn't correct
5 Execution timed out 5071 ms 9092 KB Time limit exceeded
6 Execution timed out 5051 ms 9356 KB Time limit exceeded
7 Execution timed out 5065 ms 13252 KB Time limit exceeded
8 Incorrect 25 ms 7248 KB Output isn't correct
9 Incorrect 22 ms 7384 KB Output isn't correct
10 Incorrect 21 ms 6992 KB Output isn't correct