Submission #577597

#	Time	Username	Problem	Language	Result	Execution time	Memory
577597		keta_tsimakuridze	Poklon (COCI17_poklon)	C++14	98 / 140	207 ms	16940 KiB

poklon

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, a[N], ans[N], lst[N], tree[N], n;
vector<pii> x[N];
map<int,int> f;
void upd(int id, int t) {
	for(id; id <= n; id += id & (-id)) tree[id] += t;
}
int get(int id) {
	int ans = 0;
	for(id; id >= 1; id -= id & (-id)) ans += tree[id];
	return ans;
}
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		x[l].push_back({r, i});
	}
	for(int i = n; i >= 1; i--) { 
		if(f[a[i]]) {
			upd(f[a[i]], 1); 
			if(lst[f[a[i]]]) upd(lst[f[a[i]]], -2) ;
			if(lst[lst[f[a[i]]]]) upd(lst[lst[f[a[i]]]], 1);
		} 
		lst[i] = f[a[i]];
		f[a[i]] = i;
		for(int j = 0; j < x[i].size(); j++) {
			ans[x[i][j].s] = get(x[i][j].f);
		}
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

poklon.cpp: In function 'void upd(long long int, long long int)':
poklon.cpp:13:6: warning: statement has no effect [-Wunused-value]
   13 |  for(id; id <= n; id += id & (-id)) tree[id] += t;
      |      ^~
poklon.cpp: In function 'long long int get(long long int)':
poklon.cpp:17:6: warning: statement has no effect [-Wunused-value]
   17 |  for(id; id >= 1; id -= id & (-id)) ans += tree[id];
      |      ^~
poklon.cpp: At global scope:
poklon.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main() {
      | ^~~~
poklon.cpp: In function 'int main()':
poklon.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j = 0; j < x[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 98 / 140