oj.uz

Submission #818081

# Submission time Handle Problem Language Result Execution time Memory
818081 2023-08-10T01:49:50 Z vjudge1 Poklon (COCI17_poklon) C++17
0 / 140
 5000 ms 6272 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;
	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];
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;
	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--;
	}
	cout << ans << "\n";
	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++;
		}
		cout << ans << "\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 1 ms 212 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 7 ms 356 KB Output isn't correct
4 Incorrect 34 ms 340 KB Output isn't correct
5 Incorrect 1336 ms 1744 KB Output isn't correct
6 Incorrect 1625 ms 1676 KB Output isn't correct
7 Execution timed out 5028 ms 2868 KB Time limit exceeded
8 Execution timed out 5070 ms 4012 KB Time limit exceeded
9 Execution timed out 5077 ms 5112 KB Time limit exceeded
10 Execution timed out 5048 ms 6272 KB Time limit exceeded