oj.uz

Submission #818090

# Submission time Handle Problem Language Result Execution time Memory
818090 2023-08-10T01:58:15 Z vjudge1 Poklon (COCI17_poklon) C++17
0 / 140
 5000 ms 10116 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask << (x)) & 1)
#define TASK "task"

using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int Log = sqrt(mxN);
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

struct item {
	int l;
	int r;
	int idx;
	bool operator < (const item & x) {
		if(l / Log == x.l / Log) return r < x.r;
		else return l / Log < x.l / Log;
	}
}q[mxN];

int n;
int queries;
int a[mxN];
int res[mxN];
map<int,int>cnt;

void solve() {
	cin >> n >> queries;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> q[i].l >> q[i].r,q[i].idx = i;
	sort(q + 1,q + queries + 1);
	int l = q[1].l,r = q[1].r,ans = 0;
	for (int i = q[1].l; i <= q[1].r; i++) {
		cnt[a[i]]++;
		if(cnt[a[i]] == 2) ans++;
		if(cnt[a[i]] == 3) ans--;
	}
	res[q[1].idx] = ans;
	for (int i = 2; i <= queries; i++) {
		while(l > q[i].l) {
			l--;
			if(cnt[a[l]] == 2) ans--;
			cnt[a[l]]++;
			if(cnt[a[l]] == 2) ans++;
		}
		while(l < q[i].l) {
			l++;
			if(cnt[a[l]] == 2) ans--;
			cnt[a[l]]--;
			if(cnt[a[l]] == 2) ans++;
		}
		while(r < q[i].r) {
			r++;
			if(cnt[a[r]] == 2) ans--;
			cnt[a[r]]++;
			if(cnt[a[r]] == 2) ans++;
		}
		while(r > q[i].r) {
			r--;
			if(cnt[a[r]] == 2) ans--;
			cnt[a[r]]--;
			if(cnt[a[r]] == 2) ans++;
		}
		res[q[i].idx] = ans;
	}
	for (int i = 1; i <= queries; i++) cout << res[i] << "\n";
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Incorrect 7 ms 340 KB Output isn't correct
4 Incorrect 33 ms 444 KB Output isn't correct
5 Incorrect 1340 ms 2420 KB Output isn't correct
6 Incorrect 1581 ms 2416 KB Output isn't correct
7 Execution timed out 5051 ms 4172 KB Time limit exceeded
8 Execution timed out 5065 ms 6224 KB Time limit exceeded
9 Execution timed out 5036 ms 8160 KB Time limit exceeded
10 Execution timed out 5063 ms 10116 KB Time limit exceeded