Submission #105835

#	Time	Username	Problem	Language	Result	Execution time	Memory
105835		Pro_ktmr	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	4 ms	384 KiB

arranging_tickets

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

struct SegmentTree{
private:
	int N;
	vector<int> node,lazy;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		N = 2*N-1;
		node.clear();
		lazy.clear();
		for(int i=0; i<N; i++) node.push_back(0);
		for(int i=0; i<N; i++) lazy.push_back(0);
	}
	void eval(int k, int l, int r){
		if(lazy[k] == 0) return;
		node[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, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = (N+1)/2;
		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);
			node[k] = max(node[2*k+1], node[2*k+2]);
		}
	}
	int maximum(int a, int b, int k=0, int l=0, int r=-1){
		if(r == -1) r = (N+1)/2;
		eval(k, l, r);
		if(r <= a || b <= l) return 0;
		if(a <= l && r <= b){
			return node[k];
		}
		else{
			return max(maximum(a, b, 2*k+1, l, (l+r)/2), maximum(a, b, 2*k+2, (l+r)/2, r));
		}
	}
};

int N,M;
int A[100000],B[100000],C[100000];
vector<pair<int,int>> greedy;
SegmentTree st;
int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> A[i] >> B[i] >> C[i];
		A[i]--;
		B[i]--;
		if(A[i] > B[i]) swap(A[i], B[i]);
		if(C[i] != 1) return -1;
	}
	
	//
	
	st.init(N);
	for(int i=0; i<M; i++){
		if(B[i] - A[i] > N/2){
			st.add(0, A[i], 1);
			st.add(B[i], N, 1);
			greedy.push_back(MP(A[i]+N-B[i], i));
		}
		else{
			st.add(A[i], B[i], 1);
			greedy.push_back(MP(B[i]-A[i], i));
		}
	}
	
	random_device rd;
    mt19937 g(rd());
	sort(greedy.begin(), greedy.end());
	reverse(greedy.begin(), greedy.end());
	int l = -1;
	for(int i=0; i<M-1; i++){
		if(l == -1){
			if(greedy[i].first == greedy[i+1].first) l = i;
		}
		else{
			if(greedy[i].first != greedy[i+1].first){
				shuffle(greedy.begin()+l, greedy.begin()+i+1, g);
				l = -1;
			}
		}
	}
	if(l != -1){
		shuffle(greedy.begin()+l, greedy.end(), g);
		l = -1;
	}
	
	//
	
	vector<pair<int,int>> tmp;
	for(int k=0; k<M; k++){
		int i = greedy[k].second;
		if(k+1 < M && greedy[k] == greedy[k+1]){
			if(B[i] - A[i] > N/2) tmp.push_back(MP(max(st.maximum(0, A[i]),st.maximum(B[i], N))-1 - st.maximum(A[i], B[i])-1,i));
			else tmp.push_back(MP(max(st.maximum(A[i], B[i])-1-st.maximum(0, A[i]),st.maximum(B[i], N))-1,i));
			continue;
		}
		else if(tmp.size() > 0){
			if(B[i] - A[i] > N/2) tmp.push_back(MP(max(st.maximum(0, A[i]),st.maximum(B[i], N))-1 - st.maximum(A[i], B[i])-1,i));
			else tmp.push_back(MP(max(st.maximum(A[i], B[i])-1-st.maximum(0, A[i]),st.maximum(B[i], N))-1,i));
			
			sort(tmp.begin(), tmp.end());
			while(tmp.size() > 0){
				i = tmp.back().second;
				if(B[i] - A[i] > N/2){
					if( max(st.maximum(0, A[i]),st.maximum(B[i], N))-1 >= st.maximum(A[i], B[i])+1 ){
						st.add(0, A[i], -1);
						st.add(B[i], N, -1);
						st.add(A[i], B[i], 1);
					}
					else break;
				}
				else{
					if( max(st.maximum(0, A[i]),st.maximum(B[i], N))+1 <= st.maximum(A[i], B[i])-1 ){
						st.add(0, A[i], 1);
						st.add(B[i], N, 1);
						st.add(A[i], B[i], -1);
					}
					else break;
				}
				tmp.erase(tmp.end());
			}
			continue;
		}
		if(B[i] - A[i] > N/2){
			if( max(st.maximum(0, A[i]),st.maximum(B[i], N))-1 >= st.maximum(A[i], B[i])+1 ){
				st.add(0, A[i], -1);
				st.add(B[i], N, -1);
				st.add(A[i], B[i], 1);
			}
		}
		else{
			if( max(st.maximum(0, A[i]),st.maximum(B[i], N))+1 <= st.maximum(A[i], B[i])-1 ){
				st.add(0, A[i], 1);
				st.add(B[i], N, 1);
				st.add(A[i], B[i], -1);
			}
		}
	}
	
	cout << st.maximum(0, N) << endl;
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15