oj.uz

Submission #411953

# Submission time Handle Problem Language Result Execution time Memory
411953 2021-05-26T10:41:32 Z amoo_safar Arranging Tickets (JOI17_arranging_tickets) C++17
45 / 100
 6000 ms 10828 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

vector<int> G[N], H[N];
int n, m;
int to[N], frm[N], pk[N], M = 0;

void Add_Edge(int u, int v){
	frm[M] = u;
	to[M] = v;
	pk[M] = 1;
	G[u].pb(M);
	H[v].pb(M);
	M ++;
}

struct Segment {
	int seg[N];

	Segment (){
		memset(seg, 0, sizeof seg);
	}
	void Add(int l, int r, int x){
		for(int i = l; i < r; i++)
			seg[i] += x;
	}
	int FirstPos(int l, int r){
		for(int i = l; i < r; i++)
			if(seg[i] > 0)
				return i;
		return -1;
	}
	void Print(int l, int r){
		cerr << "DS : ";
		for(int i = l; i < r; i++)
			cerr << seg[i] << ' ';
		cerr << '\n'; 
	}
};
Segment DS;

int ps[N];
int cnt[N], rcnt[N];

int MinCross(int idx){
	int mx = -1;
	for(int i = 0; i < M; i++){
		if(!pk[i] && frm[i] <= idx && idx < to[i])
			if(mx == -1 || to[mx] < to[i])
				mx = i;
	}
	return mx;
}

int res = 0;
int lnw, rnw;

void On(int u){
	for(auto in : H[u]){
		if(frm[in] >= lnw){
			DS.Add(frm[in], u, +1);
			pk[in] = 0;
		}
	}
}
void Off(int u){
	int adj;
	for(auto in : G[u]){
		adj = to[in];
		if(adj >= rnw) continue;
		if(pk[in]){
			res --;
			DS.Add(u, adj, +1);
		} else {
			DS.Add(u, adj, -1);
		}
		pk[in] = 1;
	}	
}

int Solve(int l, int r){
	lnw = l, rnw = r;

	// cerr << "-------------\n";
	// DS.Print(l, r);
	for(int i = l; i < r; i++)
		On(i);
	// cerr << "Solving " << l << ' ' << r << '\n';
	// for(int i = 0; i < M; i++)
	// 	if(!pk[i]){
	// 		debug(i);
	// 		cerr << frm[i] << " -> " << to[i] << '\n';
	// 	}
	// DS.Print(l, r);
	int pos, ed;
	while((pos = DS.FirstPos(l, r - 1)) != -1){
		// debug(pos);
		ed = MinCross(pos);
		// debug(ed);
		if(ed >= 0){
			pk[ed] = 1; res ++;
			DS.Add(frm[ed], to[ed], -2);
		} else assert(false);
	}
	int tmp = res;
	for(int i = l; i < r; i++)
		Off(i);
	return tmp;
	// memset(ps, 0, sizeof ps);
	// memcpy(rcnt, cnt, sizeof cnt);
	// memset(cnt, 0, sizeof cnt);

	// multiset<int> ms;

	// int res = 0;
	// for(int i = l; i < r - 1; i++){
	// 	for(auto x : G[i]){
	// 		if(x >= r) continue;
	// 		ps[i] ++;
	// 		ps[x] --;
	// 		ms.insert(x);
	// 		// debug(x);
	// 	}
	// 	ps[i] += ps[i - 1];
	// 	while(ps[i] > 0){
	// 		int fr = *ms.rbegin();
	// 		// debug(fr);
	// 		ms.erase(ms.find(fr));
	// 		ps[i] -= 2;
	// 		ps[fr] += 2;
	// 		res ++;
	// 		cnt[res] ++;
	// 		// cerr << i << " : " << fr << '\n';
	// 	}
	// }
	// for(int i = 0; i < N; i++)
	// 	assert(rcnt[i] <= cnt[i]);
	// // cerr << l << " , " << r << " : " << res << '\n';
	// // exit(0);
	// return res;
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int a, b, c;
	for(int i = 0; i < m; i++){
		cin >> a >> b >> c;
		assert(c == 1);
		if(a > b) swap(a, b);
		Add_Edge(a, b);
		Add_Edge(b, n + a);
		Add_Edge(n + a, n + b);
	}
	int ans = m;
	// for(int i = 1; i < n; i++) On(i);
	for(int i = 1; i <= n; i++){
		// On(n + i - 1);
		ans = min(ans, Solve(i, n + i));
		// Off(i);
		// break;
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10496 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 6 ms 10508 KB Output is correct
4 Correct 7 ms 10444 KB Output is correct
5 Correct 8 ms 10444 KB Output is correct
6 Correct 6 ms 10444 KB Output is correct
7 Correct 7 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 6 ms 10444 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10444 KB Output is correct
12 Correct 7 ms 10444 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 7 ms 10444 KB Output is correct
15 Correct 7 ms 10444 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10496 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 6 ms 10508 KB Output is correct
4 Correct 7 ms 10444 KB Output is correct
5 Correct 8 ms 10444 KB Output is correct
6 Correct 6 ms 10444 KB Output is correct
7 Correct 7 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 6 ms 10444 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10444 KB Output is correct
12 Correct 7 ms 10444 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 7 ms 10444 KB Output is correct
15 Correct 7 ms 10444 KB Output is correct
16 Correct 125 ms 10528 KB Output is correct
17 Correct 132 ms 10532 KB Output is correct
18 Correct 126 ms 10524 KB Output is correct
19 Correct 124 ms 10444 KB Output is correct
20 Correct 127 ms 10444 KB Output is correct
21 Correct 124 ms 10532 KB Output is correct
22 Correct 123 ms 10528 KB Output is correct
23 Correct 124 ms 10524 KB Output is correct
24 Correct 116 ms 10520 KB Output is correct
25 Correct 119 ms 10444 KB Output is correct
26 Correct 109 ms 10520 KB Output is correct
27 Correct 112 ms 10524 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10496 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 6 ms 10508 KB Output is correct
4 Correct 7 ms 10444 KB Output is correct
5 Correct 8 ms 10444 KB Output is correct
6 Correct 6 ms 10444 KB Output is correct
7 Correct 7 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 6 ms 10444 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10444 KB Output is correct
12 Correct 7 ms 10444 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 7 ms 10444 KB Output is correct
15 Correct 7 ms 10444 KB Output is correct
16 Correct 125 ms 10528 KB Output is correct
17 Correct 132 ms 10532 KB Output is correct
18 Correct 126 ms 10524 KB Output is correct
19 Correct 124 ms 10444 KB Output is correct
20 Correct 127 ms 10444 KB Output is correct
21 Correct 124 ms 10532 KB Output is correct
22 Correct 123 ms 10528 KB Output is correct
23 Correct 124 ms 10524 KB Output is correct
24 Correct 116 ms 10520 KB Output is correct
25 Correct 119 ms 10444 KB Output is correct
26 Correct 109 ms 10520 KB Output is correct
27 Correct 112 ms 10524 KB Output is correct
28 Execution timed out 6041 ms 10828 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10496 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 6 ms 10508 KB Output is correct
4 Correct 7 ms 10444 KB Output is correct
5 Correct 8 ms 10444 KB Output is correct
6 Correct 6 ms 10444 KB Output is correct
7 Correct 7 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 6 ms 10444 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10444 KB Output is correct
12 Correct 7 ms 10444 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 7 ms 10444 KB Output is correct
15 Correct 7 ms 10444 KB Output is correct
16 Correct 125 ms 10528 KB Output is correct
17 Correct 132 ms 10532 KB Output is correct
18 Correct 126 ms 10524 KB Output is correct
19 Correct 124 ms 10444 KB Output is correct
20 Correct 127 ms 10444 KB Output is correct
21 Correct 124 ms 10532 KB Output is correct
22 Correct 123 ms 10528 KB Output is correct
23 Correct 124 ms 10524 KB Output is correct
24 Correct 116 ms 10520 KB Output is correct
25 Correct 119 ms 10444 KB Output is correct
26 Correct 109 ms 10520 KB Output is correct
27 Correct 112 ms 10524 KB Output is correct
28 Execution timed out 6041 ms 10828 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10496 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 6 ms 10508 KB Output is correct
4 Correct 7 ms 10444 KB Output is correct
5 Correct 8 ms 10444 KB Output is correct
6 Correct 6 ms 10444 KB Output is correct
7 Correct 7 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 6 ms 10444 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10444 KB Output is correct
12 Correct 7 ms 10444 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 7 ms 10444 KB Output is correct
15 Correct 7 ms 10444 KB Output is correct
16 Correct 125 ms 10528 KB Output is correct
17 Correct 132 ms 10532 KB Output is correct
18 Correct 126 ms 10524 KB Output is correct
19 Correct 124 ms 10444 KB Output is correct
20 Correct 127 ms 10444 KB Output is correct
21 Correct 124 ms 10532 KB Output is correct
22 Correct 123 ms 10528 KB Output is correct
23 Correct 124 ms 10524 KB Output is correct
24 Correct 116 ms 10520 KB Output is correct
25 Correct 119 ms 10444 KB Output is correct
26 Correct 109 ms 10520 KB Output is correct
27 Correct 112 ms 10524 KB Output is correct
28 Execution timed out 6041 ms 10828 KB Time limit exceeded
29 Halted 0 ms 0 KB -