oj.uz

답안 #154731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154731 2019-09-24T09:08:46 Z Pro_ktmr 가로등 (APIO19_street_lamps) C++14
0 / 100
 5000 ms 42560 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

struct str{ //half open
	vector<pair<int,int>> v;
	str marge(str s){
		vector<pair<int,int>> tmp;
		for(int i=0; i<v.size(); i++) tmp.push_back(v[i]);
		for(int i=0; i<s.v.size(); i++) tmp.push_back(s.v[i]);
		sort(tmp.begin(), tmp.end());
		str ret;
		for(int i=0; i+1<tmp.size(); i++){
			if(tmp[i+1].first <= tmp[i].second-1){
				ret.v.push_back(MP(tmp[i+1].first, tmp[i].second));
			}
		}
		return ret;
	}
};

int N,Q;
string def;
int t[300000],a[300000],b[300000];
vector<int> toggle[300000];
int ans[300000] = {};

str seg[1200000] = {};
int seg_size = 1;

str full;
str query(int a, int b, int k=0, int l=0, int r=-1){
	if(r == -1) r = seg_size;
	if(r <= a || b <= l) return full;
	if(a <= l && r <= b) return seg[k];
	return query(a, b, 2*k+1, l, (l+r)/2).marge(query(a, b, 2*k+2, (l+r)/2, r));
}

int main(){
	cin >> N >> Q;
	cin >> def;
	for(int i=0; i<N; i++){
		if(def[i] == '1') toggle[i].push_back(0);
	}
	for(int i=0; i<Q; i++){
		string type;
		cin >> type;
		if(type == "toggle"){
			t[i] = 0;
			cin >> a[i];
			a[i]--;
			toggle[a[i]].push_back(i+1);
		}
		else{
			t[i] = 1;
			cin >> a[i] >> b[i];
			a[i]--; b[i]--;
		}
	}
	
	vector<pair<int,int>> d;
	while(seg_size < N) seg_size *= 2;
	for(int i=0; i<seg_size*2-1; i++) seg[i].v = d;
	for(int i=0; i<N; i++){
		str tmp;
		for(int j=0; j+1<toggle[i].size(); j+=2){
			tmp.v.push_back(MP(toggle[i][j], toggle[i][j+1]));
		}
		if(toggle[i].size()%2 == 1){
			tmp.v.push_back(MP(toggle[i].back(), N+1));
		}
		seg[seg_size-1+i] = tmp;
	}
	for(int i=seg_size-2; i>=0; i--){
		seg[i] = seg[2*i+1].marge(seg[2*i+2]);
	}

	full.v.push_back(MP(0, N+1));
	for(int i=0; i<Q; i++){
		if(t[i] == 1){
			str ans = query(a[i], b[i]);
			int ret = 0;
			for(int j=0; j<ans.v.size(); j++){
				if(ans.v[j].first >= i+1) break;
				if(ans.v[i].second >= i+1) ret += i+1 - ans.v[j].first;
				else ret += ans.v[j].second - ans.v[j].first;
				cout << ans.v[i].first << " " << ans.v[i].second << endl;
			}
			cout << ret << endl;
		}
	}
	
	return 0;
}

Compilation message

street_lamps.cpp: In member function 'str str::marge(str)':
street_lamps.cpp:10:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++) tmp.push_back(v[i]);
                ~^~~~~~~~~
street_lamps.cpp:11:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<s.v.size(); i++) tmp.push_back(s.v[i]);
                ~^~~~~~~~~~~
street_lamps.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i+1<tmp.size(); i++){
                ~~~^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j+1<toggle[i].size(); j+=2){
                ~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<ans.v.size(); j++){
                 ~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 35576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5055 ms 42560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 35704 KB Output is correct
2 Incorrect 38 ms 35704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 35576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 35576 KB Output isn't correct
2 Halted 0 ms 0 KB -