oj.uz

답안 #577599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577599 2022-06-15T06:20:36 Z keta_tsimakuridze Poklon (COCI17_poklon) C++14
140 / 140
 574 ms 41748 KB 
#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 = 5e5 + 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

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
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 10 ms 12372 KB Output is correct
5 Correct 75 ms 17968 KB Output is correct
6 Correct 82 ms 18000 KB Output is correct
7 Correct 245 ms 23984 KB Output is correct
8 Correct 344 ms 29952 KB Output is correct
9 Correct 433 ms 35800 KB Output is correct
10 Correct 574 ms 41748 KB Output is correct