oj.uz

Submission #718487

# Submission time Handle Problem Language Result Execution time Memory
718487 2023-04-04T07:54:42 Z MinhAnhnd Art Exhibition (JOI18_art) C++14
100 / 100
 614 ms 27808 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

//long R,n,m,p,totalsum = 0;
#define limit 300001


using namespace std;

/*
vector<int> graph[limit];
int timer = 0, tin[limit], euler_tour[limit];
//int segtree[800000];  // Segment tree for RMQ

void dfs(int node = 0, int parent = -1) {
	tin[node] = timer;  // The time when we first visit a node
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {
			dfs(i, node);
			euler_tour[timer++] = node;
		}
	}
}

long k = 0;
long tmax[limit*2] ={};
long tmin[limit*2] ={};
#include <bits/stdc++.h>*/

typedef long long ll;
using namespace std;

struct Line {
	bool type;
	long double x;
	ll m, c;
};

bool operator<(Line l1, Line l2) {
	if (l1.type || l2.type) return l1.x < l2.x;
	return l1.m > l2.m;
}

set<Line> cht[1];
long cht_pointer = 0;
//ll h[100001], w[100001], tot = 0, dp[100001];

bool has_prev(set<Line>::iterator it) { return it != cht[cht_pointer].begin(); }
bool has_next(set<Line>::iterator it) {
	return it != cht[cht_pointer].end() && next(it) != cht[cht_pointer].end();
}

long double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
	return (long double)(l1->c - l2->c) / (l2->m - l1->m);
}

void calc_x(set<Line>::iterator it) {
	if (has_prev(it)) {
		Line l = *it;
		l.x = intersect(prev(it), it);
		cht[cht_pointer].insert(cht[cht_pointer].erase(it), l);
	}
}

bool bad(set<Line>::iterator it) {
	if (has_next(it) && next(it)->c <= it->c) return true;
	return (has_prev(it) && has_next(it) &&
	        intersect(prev(it), next(it)) <= intersect(prev(it), it));
}

void add_line(ll m, ll c) {
	set<Line>::iterator it;

	it = cht[cht_pointer].lower_bound({0, 0, m, c});
	if (it != cht[cht_pointer].end() && it->m == m) {
		if (it->c <= c) return;
		cht[cht_pointer].erase(it);
	}

	it = cht[cht_pointer].insert({0, 0, m, c}).first;
	if (bad(it)) cht[cht_pointer].erase(it);
	else {
		while (has_prev(it) && bad(prev(it))) cht[cht_pointer].erase(prev(it));
		while (has_next(it) && bad(next(it))) cht[cht_pointer].erase(next(it));

		if (has_next(it)) calc_x(next(it));
		calc_x(it);
	}
}

ll query(ll h) {
	Line l = *prev(cht[cht_pointer].upper_bound({1, (long double)h, 0, 0}));
	return l.m * h + l.c;
}

/*long long Y,N, parent[limit] = {}, weight[limit] = {}, dp[limit] ={}, incon[limit] = {};
long long distance_[limit] = {};
long long num_child[limit] ={};
vector<long> children[limit];
stack<long> tovisit;
bool visited[limit] = {};

long moveit(ll current){
    if (!children[current].empty()) tovisit.push(current);
    long long sum = 0;
    for (auto i: children[current]){
        //cout<<i<<"checker";
        distance_[i] = distance_[current] + weight[i];
        sum += moveit(i);
        //cout<<sum<<"checker";

    }
    if (children[current].empty()) return (long long) 1;
    num_child[current] = (long long) sum;
    return sum;
}*/
#define T pair<long,long>

struct node{
    long val, sum;
};
long N, M, maxlen = 0;
vector<pair<long,long>> adj[limit];
tuple<long,long,long> temp[limit];
pair<long,long> roadid[limit];
pair<long,pair<long,long>> dist[limit];

void dijkstra(int src) {  // Source and destination
	//for (int i = 0; i < N; ++i) dist[i] = LONG_MAX;
	// Set all distances to infinity
    for (int i = 1; i <= N; i++) {dist[i].first = LONG_MAX; dist[i].second.first = -1;dist[i].second.second = -1;}
	priority_queue<T, vector<T>, greater<T>> pq;
	dist[src].first = 0;  // The shortest path from a node to itself is 0
	pq.push({0, src});

	while (pq.size()) {
		long cdist;
		long node;
		tie(cdist, node) = pq.top();

		pq.pop();
		if (cdist != dist[node].first) continue;
		for (pair<int, int> i : adj[node]) {
            long distance = roadid[i.second].first;
            if (distance == LONG_MAX) continue;
            //cout<<distance<<" "<<cdist<<" "<<i.first<<endl;
			// If we can reach a neighbouring node faster,
			// we update its minimum distance
			if (cdist + distance< dist[i.first].first) {
			    dist[i.first].second.first = node;
			    dist[i.first].second.second = i.second;
                dist[i.first].first = cdist + distance;
				pq.push({dist[i.first].first, i.first});
			}
		}
	}
}
#define lim 500001

int main(){
  long N;
  cin>>N;
  pair<long,long> pic[lim];
  pic[0].first = 0;
  pic[0].second = 0;
  long current_max = 0;
  long max_diff = LONG_MIN;
  for (long i = 1;i<=N;i++){
    cin>>pic[i].first>>pic[i].second;
  }
  sort(pic,pic+N+1);
  for (long i = 1;i<=N;i++){
    pic[i].second += pic[i-1].second;
    long now = pic[i].second - pic[i].first;
    max_diff = max(max_diff,pic[i].first-pic[i-1].second);
    current_max = max(current_max, now + max_diff);
  }
  cout<<current_max;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15060 KB Output is correct
2 Correct 9 ms 15184 KB Output is correct
3 Correct 9 ms 15132 KB Output is correct
4 Correct 11 ms 15188 KB Output is correct
5 Correct 11 ms 15180 KB Output is correct
6 Correct 9 ms 15176 KB Output is correct
7 Correct 8 ms 15184 KB Output is correct
8 Correct 9 ms 15188 KB Output is correct
9 Correct 10 ms 15176 KB Output is correct
10 Correct 9 ms 15188 KB Output is correct
11 Correct 9 ms 15060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15060 KB Output is correct
2 Correct 9 ms 15184 KB Output is correct
3 Correct 9 ms 15132 KB Output is correct
4 Correct 11 ms 15188 KB Output is correct
5 Correct 11 ms 15180 KB Output is correct
6 Correct 9 ms 15176 KB Output is correct
7 Correct 8 ms 15184 KB Output is correct
8 Correct 9 ms 15188 KB Output is correct
9 Correct 10 ms 15176 KB Output is correct
10 Correct 9 ms 15188 KB Output is correct
11 Correct 9 ms 15060 KB Output is correct
12 Correct 10 ms 15188 KB Output is correct
13 Correct 9 ms 15188 KB Output is correct
14 Correct 10 ms 15184 KB Output is correct
15 Correct 9 ms 15180 KB Output is correct
16 Correct 11 ms 15188 KB Output is correct
17 Correct 9 ms 15188 KB Output is correct
18 Correct 9 ms 15060 KB Output is correct
19 Correct 8 ms 15072 KB Output is correct
20 Correct 9 ms 15060 KB Output is correct
21 Correct 9 ms 15188 KB Output is correct
22 Correct 9 ms 15108 KB Output is correct
23 Correct 8 ms 15060 KB Output is correct
24 Correct 11 ms 15060 KB Output is correct
25 Correct 9 ms 15192 KB Output is correct
26 Correct 8 ms 15060 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15060 KB Output is correct
2 Correct 9 ms 15184 KB Output is correct
3 Correct 9 ms 15132 KB Output is correct
4 Correct 11 ms 15188 KB Output is correct
5 Correct 11 ms 15180 KB Output is correct
6 Correct 9 ms 15176 KB Output is correct
7 Correct 8 ms 15184 KB Output is correct
8 Correct 9 ms 15188 KB Output is correct
9 Correct 10 ms 15176 KB Output is correct
10 Correct 9 ms 15188 KB Output is correct
11 Correct 9 ms 15060 KB Output is correct
12 Correct 10 ms 15188 KB Output is correct
13 Correct 9 ms 15188 KB Output is correct
14 Correct 10 ms 15184 KB Output is correct
15 Correct 9 ms 15180 KB Output is correct
16 Correct 11 ms 15188 KB Output is correct
17 Correct 9 ms 15188 KB Output is correct
18 Correct 9 ms 15060 KB Output is correct
19 Correct 8 ms 15072 KB Output is correct
20 Correct 9 ms 15060 KB Output is correct
21 Correct 9 ms 15188 KB Output is correct
22 Correct 9 ms 15108 KB Output is correct
23 Correct 8 ms 15060 KB Output is correct
24 Correct 11 ms 15060 KB Output is correct
25 Correct 9 ms 15192 KB Output is correct
26 Correct 8 ms 15060 KB Output is correct
27 Correct 13 ms 15304 KB Output is correct
28 Correct 13 ms 15304 KB Output is correct
29 Correct 18 ms 15188 KB Output is correct
30 Correct 13 ms 15188 KB Output is correct
31 Correct 18 ms 15188 KB Output is correct
32 Correct 19 ms 15240 KB Output is correct
33 Correct 19 ms 15300 KB Output is correct
34 Correct 19 ms 15276 KB Output is correct
35 Correct 16 ms 15188 KB Output is correct
36 Correct 19 ms 15188 KB Output is correct
37 Correct 14 ms 15188 KB Output is correct
38 Correct 14 ms 15300 KB Output is correct
39 Correct 15 ms 15184 KB Output is correct
40 Correct 21 ms 15308 KB Output is correct
41 Correct 19 ms 15216 KB Output is correct
42 Correct 14 ms 15188 KB Output is correct
43 Correct 17 ms 15192 KB Output is correct
44 Correct 18 ms 15188 KB Output is correct
45 Correct 15 ms 15192 KB Output is correct
46 Correct 19 ms 15268 KB Output is correct
47 Correct 14 ms 15300 KB Output is correct
48 Correct 17 ms 15284 KB Output is correct
49 Correct 15 ms 15308 KB Output is correct
50 Correct 17 ms 15228 KB Output is correct
51 Correct 18 ms 15188 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15060 KB Output is correct
2 Correct 9 ms 15184 KB Output is correct
3 Correct 9 ms 15132 KB Output is correct
4 Correct 11 ms 15188 KB Output is correct
5 Correct 11 ms 15180 KB Output is correct
6 Correct 9 ms 15176 KB Output is correct
7 Correct 8 ms 15184 KB Output is correct
8 Correct 9 ms 15188 KB Output is correct
9 Correct 10 ms 15176 KB Output is correct
10 Correct 9 ms 15188 KB Output is correct
11 Correct 9 ms 15060 KB Output is correct
12 Correct 10 ms 15188 KB Output is correct
13 Correct 9 ms 15188 KB Output is correct
14 Correct 10 ms 15184 KB Output is correct
15 Correct 9 ms 15180 KB Output is correct
16 Correct 11 ms 15188 KB Output is correct
17 Correct 9 ms 15188 KB Output is correct
18 Correct 9 ms 15060 KB Output is correct
19 Correct 8 ms 15072 KB Output is correct
20 Correct 9 ms 15060 KB Output is correct
21 Correct 9 ms 15188 KB Output is correct
22 Correct 9 ms 15108 KB Output is correct
23 Correct 8 ms 15060 KB Output is correct
24 Correct 11 ms 15060 KB Output is correct
25 Correct 9 ms 15192 KB Output is correct
26 Correct 8 ms 15060 KB Output is correct
27 Correct 13 ms 15304 KB Output is correct
28 Correct 13 ms 15304 KB Output is correct
29 Correct 18 ms 15188 KB Output is correct
30 Correct 13 ms 15188 KB Output is correct
31 Correct 18 ms 15188 KB Output is correct
32 Correct 19 ms 15240 KB Output is correct
33 Correct 19 ms 15300 KB Output is correct
34 Correct 19 ms 15276 KB Output is correct
35 Correct 16 ms 15188 KB Output is correct
36 Correct 19 ms 15188 KB Output is correct
37 Correct 14 ms 15188 KB Output is correct
38 Correct 14 ms 15300 KB Output is correct
39 Correct 15 ms 15184 KB Output is correct
40 Correct 21 ms 15308 KB Output is correct
41 Correct 19 ms 15216 KB Output is correct
42 Correct 14 ms 15188 KB Output is correct
43 Correct 17 ms 15192 KB Output is correct
44 Correct 18 ms 15188 KB Output is correct
45 Correct 15 ms 15192 KB Output is correct
46 Correct 19 ms 15268 KB Output is correct
47 Correct 14 ms 15300 KB Output is correct
48 Correct 17 ms 15284 KB Output is correct
49 Correct 15 ms 15308 KB Output is correct
50 Correct 17 ms 15228 KB Output is correct
51 Correct 18 ms 15188 KB Output is correct
52 Correct 598 ms 20448 KB Output is correct
53 Correct 614 ms 27724 KB Output is correct
54 Correct 578 ms 27808 KB Output is correct
55 Correct 614 ms 27796 KB Output is correct
56 Correct 549 ms 27684 KB Output is correct
57 Correct 533 ms 27756 KB Output is correct
58 Correct 519 ms 27688 KB Output is correct
59 Correct 527 ms 27800 KB Output is correct
60 Correct 525 ms 27684 KB Output is correct
61 Correct 516 ms 27572 KB Output is correct
62 Correct 527 ms 27724 KB Output is correct
63 Correct 534 ms 27800 KB Output is correct
64 Correct 524 ms 27684 KB Output is correct
65 Correct 544 ms 27796 KB Output is correct
66 Correct 533 ms 27724 KB Output is correct
67 Correct 524 ms 27724 KB Output is correct
68 Correct 523 ms 27676 KB Output is correct