#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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |