oj.uz

답안 #60129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60129 2018-07-23T17:20:14 Z Adhyyan1252 Poklon (COCI17_poklon) C++11
140 / 140
 2612 ms 47452 KB 
#include<bits/stdc++.h>
// time 10:13, 10:38
using namespace std;
#define NMAX 5000005
int n, q;
int a[NMAX];
vector<vector<int> > ind;

struct segtree{
	vector<int> t, l;
	int sz;
	
	segtree(int n){
		sz = n;
		t.resize(4*n); l.resize(4*n);
	}
	
	inline void prop(int i, int s, int e){
		if(l[i] == 0) return;
		if(s != e){
			l[i*2] += l[i];
			l[i*2+1] += l[i];
		}
		t[i] += l[i];
		l[i] = 0;
	}
	
	void upd(int l, int r, int val){
		upd(1, 0, sz-1, l, r, val);
	}
	
	void upd(int i, int s, int e, int le, int r, int val){
		prop(i, s, e);
		if(s >= le && e <= r){
			l[i] += val;
			prop(i, s, e);
			return;
		}
		if(s > r || e < le) return;
		int m = (s + e)/2;
		upd(i*2, s, m, le, r, val);
		upd(i*2+1, m+1, e, le, r, val);
		t[i] = t[i*2] + t[i*2+1];
	}
	
	int query(int indx){
		return query(1, 0, sz-1, indx);
	}
	
	int query(int i, int s, int e, int indx){
		prop(i, s, e);
		if(s == e) return t[i];
		int m = (s + e)/2;
		if(indx <= m) return query(i*2, s, m, indx);
		else return query(i*2+1, m+1, e, indx);
	}
};


struct actions{
	int x;
	int t, b;
	int type;
	
	bool operator<(const actions& other){
		if(x != other.x) return x < other.x;
		return type < other.type;
	}
};

int main(){
	cin>>n>>q;
	map<int, int> mp;
	int cnt = 1;
	
	for(int i = 0; i < n; i++){
		cin>>a[i];
		if(mp[a[i]] == 0){
			mp[a[i]] = cnt;
			a[i] = cnt++;
		}else{
			a[i] = mp[a[i]];
		}
	}
	ind = vector<vector<int> > (cnt+1);
	for(int i = 0; i < n; i++){
		ind[a[i]].push_back(i);
	}
	mp.clear();
	vector<actions> nodes;
	for(int i = 0; i < q; i++){
		int l, r; cin>>l>>r; l--, r--;
		nodes.push_back({l, r, -1, i});
	}
	for(int i = 1; i < cnt; i++){
		if(ind[i].size() <= 1) continue;
		for(int j = 0; j < ind[i].size()-1; j++){
			// left point is j, right point is j+2
			int l = (j == 0?0:(ind[i][j-1]+1));
			int r = (j == ind[i].size()-2)?n-1:(ind[i][j+2]-1);
			nodes.push_back({l, r, ind[i][j+1], -1});
			nodes.push_back({ind[i][j]+1, r, ind[i][j+1], -2});
		}
	}
	sort(nodes.begin(), nodes.end());
	int ans[q];
	segtree st(n);
	for(actions a: nodes){
		if(a.type < 0){
			st.upd(a.b, a.t, (a.type==-1)?1:-1);
		}else{
			ans[a.type] = st.query(a.t);
		}
	}
	for(int i = 0; i < q; i++){
		cout<<ans[i]<<endl;
	}
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < ind[i].size()-1; j++){
                  ~~^~~~~~~~~~~~~~~~~
poklon.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    int r = (j == ind[i].size()-2)?n-1:(ind[i][j+2]-1);
             ~~^~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 6 ms 560 KB Output is correct
4 Correct 20 ms 1020 KB Output is correct
5 Correct 412 ms 9888 KB Output is correct
6 Correct 423 ms 9936 KB Output is correct
7 Correct 1004 ms 19448 KB Output is correct
8 Correct 1572 ms 29432 KB Output is correct
9 Correct 1909 ms 38716 KB Output is correct
10 Correct 2612 ms 47452 KB Output is correct