Submission #411998

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411998	2021-05-26T11:58:44 Z	amoo_safar	Arranging Tickets (JOI17_arranging_tickets)	C++17	45 / 100	6000 ms	10828 KB

arranging_tickets

// 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);
	// 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 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, 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	6 ms	10444 KB	Output is correct
2	Correct	7 ms	10500 KB	Output is correct
3	Correct	7 ms	10444 KB	Output is correct
4	Correct	7 ms	10444 KB	Output is correct
5	Correct	7 ms	10500 KB	Output is correct
6	Correct	7 ms	10500 KB	Output is correct
7	Correct	7 ms	10444 KB	Output is correct
8	Correct	7 ms	10504 KB	Output is correct
9	Correct	7 ms	10444 KB	Output is correct
10	Correct	7 ms	10500 KB	Output is correct
11	Correct	7 ms	10444 KB	Output is correct
12	Correct	7 ms	10444 KB	Output is correct
13	Correct	6 ms	10444 KB	Output is correct
14	Correct	7 ms	10512 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	6 ms	10444 KB	Output is correct
2	Correct	7 ms	10500 KB	Output is correct
3	Correct	7 ms	10444 KB	Output is correct
4	Correct	7 ms	10444 KB	Output is correct
5	Correct	7 ms	10500 KB	Output is correct
6	Correct	7 ms	10500 KB	Output is correct
7	Correct	7 ms	10444 KB	Output is correct
8	Correct	7 ms	10504 KB	Output is correct
9	Correct	7 ms	10444 KB	Output is correct
10	Correct	7 ms	10500 KB	Output is correct
11	Correct	7 ms	10444 KB	Output is correct
12	Correct	7 ms	10444 KB	Output is correct
13	Correct	6 ms	10444 KB	Output is correct
14	Correct	7 ms	10512 KB	Output is correct
15	Correct	7 ms	10444 KB	Output is correct
16	Correct	128 ms	10500 KB	Output is correct
17	Correct	129 ms	10444 KB	Output is correct
18	Correct	127 ms	10536 KB	Output is correct
19	Correct	144 ms	10532 KB	Output is correct
20	Correct	131 ms	10444 KB	Output is correct
21	Correct	125 ms	10444 KB	Output is correct
22	Correct	131 ms	10540 KB	Output is correct
23	Correct	132 ms	10564 KB	Output is correct
24	Correct	118 ms	10524 KB	Output is correct
25	Correct	119 ms	10444 KB	Output is correct
26	Correct	114 ms	10444 KB	Output is correct
27	Correct	118 ms	10444 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	7 ms	10500 KB	Output is correct
3	Correct	7 ms	10444 KB	Output is correct
4	Correct	7 ms	10444 KB	Output is correct
5	Correct	7 ms	10500 KB	Output is correct
6	Correct	7 ms	10500 KB	Output is correct
7	Correct	7 ms	10444 KB	Output is correct
8	Correct	7 ms	10504 KB	Output is correct
9	Correct	7 ms	10444 KB	Output is correct
10	Correct	7 ms	10500 KB	Output is correct
11	Correct	7 ms	10444 KB	Output is correct
12	Correct	7 ms	10444 KB	Output is correct
13	Correct	6 ms	10444 KB	Output is correct
14	Correct	7 ms	10512 KB	Output is correct
15	Correct	7 ms	10444 KB	Output is correct
16	Correct	128 ms	10500 KB	Output is correct
17	Correct	129 ms	10444 KB	Output is correct
18	Correct	127 ms	10536 KB	Output is correct
19	Correct	144 ms	10532 KB	Output is correct
20	Correct	131 ms	10444 KB	Output is correct
21	Correct	125 ms	10444 KB	Output is correct
22	Correct	131 ms	10540 KB	Output is correct
23	Correct	132 ms	10564 KB	Output is correct
24	Correct	118 ms	10524 KB	Output is correct
25	Correct	119 ms	10444 KB	Output is correct
26	Correct	114 ms	10444 KB	Output is correct
27	Correct	118 ms	10444 KB	Output is correct
28	Execution timed out	6054 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	6 ms	10444 KB	Output is correct
2	Correct	7 ms	10500 KB	Output is correct
3	Correct	7 ms	10444 KB	Output is correct
4	Correct	7 ms	10444 KB	Output is correct
5	Correct	7 ms	10500 KB	Output is correct
6	Correct	7 ms	10500 KB	Output is correct
7	Correct	7 ms	10444 KB	Output is correct
8	Correct	7 ms	10504 KB	Output is correct
9	Correct	7 ms	10444 KB	Output is correct
10	Correct	7 ms	10500 KB	Output is correct
11	Correct	7 ms	10444 KB	Output is correct
12	Correct	7 ms	10444 KB	Output is correct
13	Correct	6 ms	10444 KB	Output is correct
14	Correct	7 ms	10512 KB	Output is correct
15	Correct	7 ms	10444 KB	Output is correct
16	Correct	128 ms	10500 KB	Output is correct
17	Correct	129 ms	10444 KB	Output is correct
18	Correct	127 ms	10536 KB	Output is correct
19	Correct	144 ms	10532 KB	Output is correct
20	Correct	131 ms	10444 KB	Output is correct
21	Correct	125 ms	10444 KB	Output is correct
22	Correct	131 ms	10540 KB	Output is correct
23	Correct	132 ms	10564 KB	Output is correct
24	Correct	118 ms	10524 KB	Output is correct
25	Correct	119 ms	10444 KB	Output is correct
26	Correct	114 ms	10444 KB	Output is correct
27	Correct	118 ms	10444 KB	Output is correct
28	Execution timed out	6054 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	6 ms	10444 KB	Output is correct
2	Correct	7 ms	10500 KB	Output is correct
3	Correct	7 ms	10444 KB	Output is correct
4	Correct	7 ms	10444 KB	Output is correct
5	Correct	7 ms	10500 KB	Output is correct
6	Correct	7 ms	10500 KB	Output is correct
7	Correct	7 ms	10444 KB	Output is correct
8	Correct	7 ms	10504 KB	Output is correct
9	Correct	7 ms	10444 KB	Output is correct
10	Correct	7 ms	10500 KB	Output is correct
11	Correct	7 ms	10444 KB	Output is correct
12	Correct	7 ms	10444 KB	Output is correct
13	Correct	6 ms	10444 KB	Output is correct
14	Correct	7 ms	10512 KB	Output is correct
15	Correct	7 ms	10444 KB	Output is correct
16	Correct	128 ms	10500 KB	Output is correct
17	Correct	129 ms	10444 KB	Output is correct
18	Correct	127 ms	10536 KB	Output is correct
19	Correct	144 ms	10532 KB	Output is correct
20	Correct	131 ms	10444 KB	Output is correct
21	Correct	125 ms	10444 KB	Output is correct
22	Correct	131 ms	10540 KB	Output is correct
23	Correct	132 ms	10564 KB	Output is correct
24	Correct	118 ms	10524 KB	Output is correct
25	Correct	119 ms	10444 KB	Output is correct
26	Correct	114 ms	10444 KB	Output is correct
27	Correct	118 ms	10444 KB	Output is correct
28	Execution timed out	6054 ms	10828 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-