oj.uz

Submission #412083

# Submission time Handle Problem Language Result Execution time Memory
412083 2021-05-26T13:37:59 Z amoo_safar Arranging Tickets (JOI17_arranging_tickets) C++17
45 / 100
 6000 ms 10856 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;
	}
	int Max(int l, int r){
		return *max_element(seg + l, seg + r);
	}
	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 nx;
int Solve(int l, int r){
	lnw = l, rnw = r;

	// cerr << "-------------\n";
	// DS.Print(l, r);
	// On(r - 1);
	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 Calc(int i){
	return Solve(i, i + n);
}

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;
	lnw = 1, rnw = n + 1;
	// for(int i = 1; i < n; i++) On(i);
	for(int i = 1; i <= n; i++){
		// On(n + i - 1);
		ans = min(ans, Calc(i));
		// Off(i);
		// break;
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Correct 6 ms 10444 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 8 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 8 ms 10444 KB Output is correct
10 Correct 7 ms 10444 KB Output is correct
11 Correct 7 ms 10444 KB Output is correct
12 Correct 6 ms 10444 KB Output is correct
13 Correct 7 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 7 ms 10416 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Correct 6 ms 10444 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 8 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 8 ms 10444 KB Output is correct
10 Correct 7 ms 10444 KB Output is correct
11 Correct 7 ms 10444 KB Output is correct
12 Correct 6 ms 10444 KB Output is correct
13 Correct 7 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 7 ms 10416 KB Output is correct
16 Correct 127 ms 10444 KB Output is correct
17 Correct 128 ms 10444 KB Output is correct
18 Correct 129 ms 10528 KB Output is correct
19 Correct 136 ms 10444 KB Output is correct
20 Correct 158 ms 10444 KB Output is correct
21 Correct 126 ms 10524 KB Output is correct
22 Correct 140 ms 10444 KB Output is correct
23 Correct 139 ms 10572 KB Output is correct
24 Correct 117 ms 10524 KB Output is correct
25 Correct 117 ms 10444 KB Output is correct
26 Correct 120 ms 10524 KB Output is correct
27 Correct 116 ms 10520 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Correct 6 ms 10444 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 8 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 8 ms 10444 KB Output is correct
10 Correct 7 ms 10444 KB Output is correct
11 Correct 7 ms 10444 KB Output is correct
12 Correct 6 ms 10444 KB Output is correct
13 Correct 7 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 7 ms 10416 KB Output is correct
16 Correct 127 ms 10444 KB Output is correct
17 Correct 128 ms 10444 KB Output is correct
18 Correct 129 ms 10528 KB Output is correct
19 Correct 136 ms 10444 KB Output is correct
20 Correct 158 ms 10444 KB Output is correct
21 Correct 126 ms 10524 KB Output is correct
22 Correct 140 ms 10444 KB Output is correct
23 Correct 139 ms 10572 KB Output is correct
24 Correct 117 ms 10524 KB Output is correct
25 Correct 117 ms 10444 KB Output is correct
26 Correct 120 ms 10524 KB Output is correct
27 Correct 116 ms 10520 KB Output is correct
28 Execution timed out 6015 ms 10856 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Correct 6 ms 10444 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 8 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 8 ms 10444 KB Output is correct
10 Correct 7 ms 10444 KB Output is correct
11 Correct 7 ms 10444 KB Output is correct
12 Correct 6 ms 10444 KB Output is correct
13 Correct 7 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 7 ms 10416 KB Output is correct
16 Correct 127 ms 10444 KB Output is correct
17 Correct 128 ms 10444 KB Output is correct
18 Correct 129 ms 10528 KB Output is correct
19 Correct 136 ms 10444 KB Output is correct
20 Correct 158 ms 10444 KB Output is correct
21 Correct 126 ms 10524 KB Output is correct
22 Correct 140 ms 10444 KB Output is correct
23 Correct 139 ms 10572 KB Output is correct
24 Correct 117 ms 10524 KB Output is correct
25 Correct 117 ms 10444 KB Output is correct
26 Correct 120 ms 10524 KB Output is correct
27 Correct 116 ms 10520 KB Output is correct
28 Execution timed out 6015 ms 10856 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Correct 6 ms 10444 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 8 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 8 ms 10444 KB Output is correct
10 Correct 7 ms 10444 KB Output is correct
11 Correct 7 ms 10444 KB Output is correct
12 Correct 6 ms 10444 KB Output is correct
13 Correct 7 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 7 ms 10416 KB Output is correct
16 Correct 127 ms 10444 KB Output is correct
17 Correct 128 ms 10444 KB Output is correct
18 Correct 129 ms 10528 KB Output is correct
19 Correct 136 ms 10444 KB Output is correct
20 Correct 158 ms 10444 KB Output is correct
21 Correct 126 ms 10524 KB Output is correct
22 Correct 140 ms 10444 KB Output is correct
23 Correct 139 ms 10572 KB Output is correct
24 Correct 117 ms 10524 KB Output is correct
25 Correct 117 ms 10444 KB Output is correct
26 Correct 120 ms 10524 KB Output is correct
27 Correct 116 ms 10520 KB Output is correct
28 Execution timed out 6015 ms 10856 KB Time limit exceeded
29 Halted 0 ms 0 KB -