oj.uz

Submission #415696

# Submission time Handle Problem Language Result Execution time Memory
415696 2021-06-01T11:41:11 Z alishahali1382 Arranging Tickets (JOI17_arranging_tickets) C++14
10 / 100
 22 ms 3116 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=17;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], B[MAXN], C[MAXN];
int ps[MAXN], ps2[MAXN];
vector<int> vec2[MAXN];

bool Check2(vector<pii> &vec, int ted){
	for (int i=1; i<n; i++) vec2[i].clear(), ps2[i]=ps[i]+ted;
	for (pii p:vec) vec2[p.first].pb(p.second);
	priority_queue<int/*, vector<int>, greater<int>*/> pq;
	for (int i=1; i<n; i++){
		for (int j:vec2[i]) pq.push(j);
		while (ps2[i]>ans){
			if (pq.empty() || !(ted--)) return 0;
			int j=pq.top();
			if (j<i) return 0;
			while (j>i) ps2[--j]-=2;
		}
	}
	return 1;
}
bool Check(){
	memset(ps, 0, sizeof(ps));
	for (int i=1; i<=m; i++){
		ps[A[i]]++;
		ps[B[i]]--;
	}
	for (int i=1; i<=n; i++) ps[i]+=ps[i-1];
//	cerr<<"ps: ";for (int i=1; i<=n; i++) cerr<<ps[i]<<" \n"[i==n];
	int mx=*max_element(ps+1, ps+n);
	if (mx<=ans) return 1; // useless TOF
	for (int i=1; i<n; i++) if (ps[i]==mx){ // FFS be small
		vector<pii> vec;
		for (int j=1; j<=m; j++) if (A[j]<=i && i<B[j]) vec.pb({A[j], B[j]});
		for (int j=1; j<=vec.size() && j<=ans; j++) if (Check2(vec, j)) return 1;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=m; i++){
		cin>>A[i]>>B[i]>>C[i];
		if (A[i]>B[i]) swap(A[i], B[i]);
		assert(C[i]==1);
	}
	int dwn=0, up=m;
	while (up-dwn>1){
		ans=(dwn+up)>>1;
		if (Check()) up=ans;
		else dwn=ans;
	}
	cout<<up<<"\n";
	
	return 0;
}
/*
3 3
1 2 1
2 3 1
3 1 1

6 3
1 4 1
2 5 1
3 6 1

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 3 ms 3060 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 3 ms 3064 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 3 ms 3064 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 3 ms 3064 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 3 ms 3060 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 3 ms 3064 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 3 ms 3064 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 3 ms 3064 KB Output is correct
16 Correct 19 ms 3116 KB Output is correct
17 Correct 14 ms 3092 KB Output is correct
18 Correct 18 ms 3096 KB Output is correct
19 Correct 22 ms 3092 KB Output is correct
20 Correct 17 ms 3092 KB Output is correct
21 Incorrect 16 ms 3084 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 3 ms 3060 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 3 ms 3064 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 3 ms 3064 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 3 ms 3064 KB Output is correct
16 Correct 19 ms 3116 KB Output is correct
17 Correct 14 ms 3092 KB Output is correct
18 Correct 18 ms 3096 KB Output is correct
19 Correct 22 ms 3092 KB Output is correct
20 Correct 17 ms 3092 KB Output is correct
21 Incorrect 16 ms 3084 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 3 ms 3060 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 3 ms 3064 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 3 ms 3064 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 3 ms 3064 KB Output is correct
16 Correct 19 ms 3116 KB Output is correct
17 Correct 14 ms 3092 KB Output is correct
18 Correct 18 ms 3096 KB Output is correct
19 Correct 22 ms 3092 KB Output is correct
20 Correct 17 ms 3092 KB Output is correct
21 Incorrect 16 ms 3084 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 3 ms 3060 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 3 ms 3020 KB Output is correct
9 Correct 3 ms 3064 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 3 ms 3064 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 3 ms 3064 KB Output is correct
16 Correct 19 ms 3116 KB Output is correct
17 Correct 14 ms 3092 KB Output is correct
18 Correct 18 ms 3096 KB Output is correct
19 Correct 22 ms 3092 KB Output is correct
20 Correct 17 ms 3092 KB Output is correct
21 Incorrect 16 ms 3084 KB Output isn't correct
22 Halted 0 ms 0 KB -