oj.uz

Submission #941317

# Submission time Handle Problem Language Result Execution time Memory
941317 2024-03-08T13:31:58 Z phamducminh Poklon (COCI17_poklon) C++17
140 / 140
 1604 ms 15308 KB 
#include <bits/stdc++.h> 
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define ii pair<int, int>
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define file(name) if(fopen(name".INP", "r")) {freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);}
#define usaco(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}
 
#define el "\n"
#define fi first
#define se second
 
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
 
const int N = 5e5 + 12;
 
struct query {
	int l, r, ind;
};
 
int n, q, bz = 700, curleft, curright, cur = 0;
int a[N], ans[N], cnt[N];
vector<int> b, v;
query qry[N];
 
bool cmp(query x, query y) {
	return (mp(x.l / bz, x.r) < mp(y.l / bz, y.r));
}
 
void add(int idx) {
	if(idx == 0) return;
	int x = a[idx];
	if(cnt[x] == 2) cur--;
	cnt[x]++;
	if(cnt[x] == 2) cur++;
}
 
void remove(int idx) {
	if(idx == 0) return;
	int x = a[idx];
	if(cnt[x] == 2) cur--;
	cnt[x]--;
	if(cnt[x] == 2) cur++;
}
 
void mo(int idx) {
	int left = qry[idx].l, right = qry[idx].r;
 
	while(curleft < left) {
		remove(curleft);
		curleft++;
	}
 
	while(left < curleft) {
		curleft--;
		add(curleft);
	}
 
	while(right < curright) {
		remove(curright);
		curright--;
	}
 
	while(curright < right) {
		curright++;
		add(curright);
	}
}
 
void solve() { 
	cin >> n >> q;
 
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		b.push_back(a[i]);
	}    
 
	sort(all(b));
	b.resize(unique(all(b)) - b.begin());
 
	for(int i = 1; i <= n; i++)
		a[i] = lower_bound(all(b), a[i]) - b.begin() + 1;
 
	for(int i = 1; i <= q; i++)
		cin >> qry[i].l >> qry[i].r, 
		qry[i].ind = i;
 
	sort(qry + 1, qry + 1 + q, cmp);
 
	for(int i = 1; i <= q; i++) {
		mo(i);
		ans[qry[i].ind] = cur;
	}
 
	for(int i = 1; i <= q; i++)
		cout << ans[i] << el;
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
    cerr << el<< "Time elapsed: " << (1000.0 * clock() / CLOCKS_PER_SEC) << "ms.\n";
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 7 ms 6748 KB Output is correct
5 Correct 151 ms 9356 KB Output is correct
6 Correct 156 ms 9428 KB Output is correct
7 Correct 408 ms 12188 KB Output is correct
8 Correct 745 ms 13256 KB Output is correct
9 Correct 1122 ms 14280 KB Output is correct
10 Correct 1604 ms 15308 KB Output is correct