oj.uz

Submission #549298

# Submission time Handle Problem Language Result Execution time Memory
549298 2022-04-15T14:57:10 Z brunnorezendes Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 1 ms 1192 KB 
#include <bits/stdc++.h>
#define maxn 200000
#define s second
#define f first

using namespace std;

typedef pair<int,int> ii;
typedef vector <ii> vii;
typedef vector <int> vi;

int seg[4*maxn], lazy[4*maxn];

void unlazy(int u){
	seg[u]+=lazy[u];
	lazy[(2*u)] += lazy[u];
	lazy[(2*u)+1] += lazy[u];
	lazy[u]=0;
}

void update(int u, int l, int r, int ql, int qr, int c){
	int mid;
	mid = (l+r)/2;
	unlazy(u);
	if(ql>r || qr<l) mid=0;
	else{
		if(l>=ql && r<=qr) lazy[u]+=c;
		else{
			update(2*u, l, mid, ql, qr, c);
			update((2*u)+1, mid+1, r, ql, qr, c);
			seg[u] = max(seg[2*u], seg[(2*u)+1]);
		}
		unlazy(u);
	}
}

int main(){
	int n, i, m, people[maxn], a, b, ant, atu;
	vii stations, v;
	cin >> n >> m;
	for(i=0;i<m;i++){
		cin >> a >> b >> people[i];
		if(a>b) swap(a,b);
		stations.push_back({a, b});
		v.push_back({b-a, i});
	}
	sort(v.begin(), v.end());
	for(i=0;i<m;i++){
		update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, people[v[i].s]);
	}
	for(i=m-1;i>=0;i--){
		unlazy(1);
		ant = seg[1];
		update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, -people[v[i].s]);
		if(stations[v[i].s].f) update(1, 0, n-1, 0, stations[v[i].s].f-1, people[v[i].s]);
		update(1, 0, n-1, stations[v[i].s].s, n-1, people[v[i].s]);
		unlazy(1);
		atu = seg[1];
		if(ant<=atu){
			update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, people[v[i].s]);
			if(stations[v[i].s].f) update(1, 0, n-1, 0, stations[v[i].s].f-1, -people[v[i].s]);
			update(1, 0, n-1, stations[v[i].s].s, n-1, -people[v[i].s]);
		}
	}
	cout << seg[1] << endl;
	return (0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1088 KB Output is correct
6 Correct 1 ms 1088 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1088 KB Output is correct
9 Correct 1 ms 1192 KB Output is correct
10 Correct 1 ms 1088 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Incorrect 1 ms 1084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1088 KB Output is correct
6 Correct 1 ms 1088 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1088 KB Output is correct
9 Correct 1 ms 1192 KB Output is correct
10 Correct 1 ms 1088 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Incorrect 1 ms 1084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1088 KB Output is correct
6 Correct 1 ms 1088 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1088 KB Output is correct
9 Correct 1 ms 1192 KB Output is correct
10 Correct 1 ms 1088 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Incorrect 1 ms 1084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1088 KB Output is correct
6 Correct 1 ms 1088 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1088 KB Output is correct
9 Correct 1 ms 1192 KB Output is correct
10 Correct 1 ms 1088 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Incorrect 1 ms 1084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1088 KB Output is correct
6 Correct 1 ms 1088 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1088 KB Output is correct
9 Correct 1 ms 1192 KB Output is correct
10 Correct 1 ms 1088 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Incorrect 1 ms 1084 KB Output isn't correct
13 Halted 0 ms 0 KB -