Submission #1229837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229837		salmon	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	0 ms	320 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;

int N;
int M;
int l[3100];
int r[3100];
int pre[3100];
int diff[3100];
bool visited[3100];

int main(){

	scanf(" %d",&N);
	scanf(" %d",&M);
	
	for(int i = 1; i <= M; i++){
		scanf(" %d",&l[i]);
		scanf(" %d",&r[i]);
		
		if(l[i] > r[i]) swap(l[i],r[i]);
		
		r[i]--;
		
		int h;
		scanf(" %d",&h);
	}
	
	for(int i = 0; i <= N; i++) pre[i] = 0;
	
	for(int i = 1; i <= M; i++){
		pre[l[i]]++;
		pre[r[i] + 1]--;
	}
	
	pre[0] = 0;
	
	for(int i = 1; i <= N; i++){
		pre[i] += pre[i - 1]; 
	}
	
	pair<int,int> big = {-1,-1};
	
	for(int i = 1; i <= N; i++){
		big = max(big,{pre[i],i});
	}
	
	int in = big.second;
	
	vector<pair<int,int>> proc;
		
	int big1 = -1;
	
	for(int i = 1; i <= in; i++){
		if(big1 < pre[i]){
			proc.push_back({pre[i],i});
			big1 = pre[i];
		}
	}
		
	int s = 1;
	int e = M + 1;
	
	while(s != e){
		int m = (s + e)/2;
		
		for(int i = 0; i <= N; i++) diff[i] = 0;
		
		int num = 0;
		
		for(int i = 0; i <= M; i++) visited[i] = false;
		
		for(pair<int,int> ii : proc){
			while(true){
				if(ii.first + big.first - num * 2 - m  <= m) break;
				
				pair<int,int> chose = {0,-1};
				
				for(int i = 1; i <= M; i++){
					if(!visited[i] && l[i] <= ii.second){
						chose = max(chose,{r[i],i});
					}
				}
				
				if(chose.second == -1){
					break;
				}
				
				num++;
				visited[chose.second] = true;
				diff[1]++;
				diff[l[chose.second]]--;
				diff[l[chose.second]]--;
				diff[r[chose.second] + 1]++;
				diff[r[chose.second] + 1]++;
			}
		}
		bool die = false;
		
		for(int i = 1; i <= N; i++){
			diff[i] += diff[i - 1];
			printf("%d ",diff[i] + pre[i]);
			if(diff[i] + pre[i] > m) die = true;
		}

		printf("\n%d %d %d\n",s,e,m);

		if(die){
			s = m + 1;
		}
		else e = m;
	}
	
	printf("%d\n",s);
}
/*
3 3
1 2 1
2 3 1
3 1 1
 */

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
arranging_tickets.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
arranging_tickets.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf(" %d",&l[i]);
      |                 ~~~~~^~~~~~~~~~~~~
arranging_tickets.cpp:19:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |                 scanf(" %d",&r[i]);
      |                 ~~~~~^~~~~~~~~~~~~
arranging_tickets.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~

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