Submission #105720

#	Time	Username	Problem	Language	Result	Execution time	Memory
105720		Pro_ktmr	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	100 / 100	1096 ms	51560 KiB

worst_reporter2

#include"bits/stdc++.h"
using namespace std;
#define MP(a,b) make_pair(a,b)

//RAQ RMQ セグメント木
struct SegmentTree{
private:
	int n;
	vector<long long> nodes,lazy;
public:
	void init(int N){ //初期化する O(N)
		nodes.clear();
		lazy.clear();
		n = 1;
		while(n < N) n *= 2;
		n = 2 * n -1;
		for(int i=0; i<n; i++){
			nodes.push_back(0);
			lazy.push_back(0);
		}
	}
	void eval(int k, int l, int r){ //遅延評価を行う
		if(lazy[k] == 0) return;
		nodes[k] += lazy[k];
		if(r-l > 1){
			lazy[2*k+1] += lazy[k];
			lazy[2*k+2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void add(int a, int b, long long x, int k=0, int l=0, int r=-1){ //区間に対して値を加算する O(log N)
		if(r == -1) r = n/2+1;
		eval(k, l, r);
		if(r <= a || b <= l) return; //交差する場合
		if(a <= l && r <= b){ //完全に含む場合
			lazy[k] += x;
			eval(k, l, r);
		}
		else{
			add(a, b, x, 2*k+1, l, (l+r)/2);
			add(a, b, x, 2*k+2, (l+r)/2, r);
			nodes[k] = min(nodes[2*k+1], nodes[2*k+2]);
		}
	}
	long long minimum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
		//cout << a << " " << b << " " << k << " " << l << " " << r << endl;
		if(r == -1) r = n/2+1;
		if(r <= a || b <= l) return LLONG_MAX; //交差する場合
		eval(k, l, r);
		if(a <= l && r <= b) return nodes[k]; //完全に含む場合
		long long valueL = minimum(a, b, k*2+1, l, (l+r)/2);
		long long valueR = minimum(a, b, k*2+2, (l+r)/2, r);
		return min(valueL, valueR);
	}
	void print(){
		cout << "nodes" << endl;
		int sp = n;
		int nx = 0;
		for(int i=0; i<nodes.size(); i++){
			cout << nodes[i];
			for(int j=0; j<sp; j++) cout << " ";
			if(i == nx){
				nx = nx*2+2;
				sp /= 2;
				cout << endl;
			}
		}
		cout << "lazy" << endl;
		sp = n;
		nx = 0;
		for(int i=0; i<lazy.size(); i++){
			cout << lazy[i];
			for(int j=0; j<sp; j++) cout << " ";
			if(i == nx){
				nx = nx*2+2;
				sp /= 2;
				cout << endl;
			}
		}
		cout << endl;
	}
};

int N;
int A[200000],B[200000],C[200000],D[200000];
set<pair<int,int>> nokori[200000];
bool already1[200000] = {};
bool already2[200000] = {};
vector<int> all,diff;
SegmentTree st;

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", A+i, B+i);
		A[i]--;
		all.push_back(B[i]);
		nokori[A[i]].insert(MP(B[i],i));
	}
	for(int i=0; i<N; i++){
		scanf("%d%d", C+i, D+i);
		C[i]--;
		all.push_back(D[i]);
	}
	sort(all.begin(), all.end());

	//

	vector<int> moto,ato;
	for(int i=N-1; i>=0; i--){
		if(!already1[i]) moto.push_back(B[i]);
	}
	for(int i=N-1; i>=0; i--){
		if(!already2[i]) ato.push_back(D[i]);
	}
	int idx1 = 0;
	int idx2 = 0;
	for(int i=0; i<all.size(); i++){
		while(idx1 < moto.size() && moto[idx1] <= all[i]) idx1++;
		while(idx2 < ato.size() && ato[idx2] <= all[i]) idx2++;
		diff.push_back(idx1-idx2);
	}

	st.init(all.size());
	for(int i=0; i<all.size(); i++) st.add(i, i+1, diff[i]);

	//
	
	int ans = N;
	for(int i=N-1; i>=0; i--){
		auto itr = nokori[C[i]].upper_bound(MP(D[i]+1, -1));
		int tmp;
		if(itr == nokori[C[i]].begin()) tmp = -1;
		else{
			itr--;
			tmp = itr->second;
			nokori[C[i]].erase(itr);
			already1[tmp] = false;
			already2[i] = false;
			st.add(lower_bound(all.begin(), all.end(), B[tmp])-all.begin(), all.size(), -1);
			st.add(lower_bound(all.begin(), all.end(), D[i])-all.begin(), all.size(), +1);
		}
		if(st.minimum(0,all.size()) >= 0 && tmp >= 0){
			ans--;
		}
		else{
			if(tmp >= 0){
				nokori[C[i]].insert(MP(B[tmp],tmp));
				already1[tmp] = false;
				already2[i] = false;
				st.add(lower_bound(all.begin(), all.end(), B[tmp])-all.begin(), all.size(), +1);
				st.add(lower_bound(all.begin(), all.end(), D[i])-all.begin(), all.size(), -1);
			}
		}
	}
	printf("%d\n", ans);

	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In member function 'void SegmentTree::print()':
worst_reporter2.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<nodes.size(); i++){
                ~^~~~~~~~~~~~~
worst_reporter2.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<lazy.size(); i++){
                ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++){
               ~^~~~~~~~~~~
worst_reporter2.cpp:119:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx1 < moto.size() && moto[idx1] <= all[i]) idx1++;
         ~~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx2 < ato.size() && ato[idx2] <= all[i]) idx2++;
         ~~~~~^~~~~~~~~~~~
worst_reporter2.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++) st.add(i, i+1, diff[i]);
               ~^~~~~~~~~~~
worst_reporter2.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", A+i, B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", C+i, D+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40