답안 #1008652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008652	2024-06-26T16:17:45 Z	fimh	Art Exhibition (JOI18_art)	C++14	50 / 100	31 ms	6228 KB

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)a.size()

const ll N = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll n;
pll a[N];

struct SegmentTree{
    ll st[N << 2], lz[N << 2];
    void apply(ll id, ll k){
        st[id] += k;
        lz[id] += k;
    }
    void push(ll id){
        apply(id << 1, lz[id]);
        apply(id << 1 | 1, lz[id]);
        lz[id] = 0;
    }
    void upd(ll id, ll l, ll r, ll u, ll v, ll x){
        if (r < u || l > v) return;
        if (u <= l && r <= v){
            apply(id, x);
            return;
        }
        push(id);
        ll mid = l + r >> 1;
        upd(id << 1, l, mid, u, v, x);
        upd(id << 1 | 1, mid + 1, r, u, v, x);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    ll get(ll id, ll l, ll r, ll u, ll v){
        if (r < u || l > v) return -inf;
        if (u <= l && r <= v) return st[id];
        push(id);
        ll mid = l + r >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
} st;

void Solve(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1);
    ll ans = -inf;
    for (int i = 1; i <= n; ++i){
        st.upd(1, 1, n, 1, i, a[i].se);
        st.upd(1, 1, n, i, i, a[i].fi);
        ans = max(ans, st.get(1, 1, n, 1, i) - a[i].fi);
    }
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("FILE.inp", "r", stdin);
//    freopen("FILE.out", "w", stdout);
    ll t = 1; // cin >> t;
    while (t--) Solve();
}

Compilation message

art.cpp: In member function 'void SegmentTree::upd(ll, ll, ll, ll, ll, ll)':
art.cpp:37:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         ll mid = l + r >> 1;
      |                  ~~^~~
art.cpp: In member function 'll SegmentTree::get(ll, ll, ll, ll, ll)':
art.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         ll mid = l + r >> 1;
      |                  ~~^~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	600 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	600 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	3 ms	848 KB	Output is correct
28	Correct	3 ms	860 KB	Output is correct
29	Correct	3 ms	856 KB	Output is correct
30	Correct	2 ms	860 KB	Output is correct
31	Correct	2 ms	928 KB	Output is correct
32	Correct	2 ms	860 KB	Output is correct
33	Correct	2 ms	860 KB	Output is correct
34	Correct	2 ms	860 KB	Output is correct
35	Correct	3 ms	856 KB	Output is correct
36	Correct	3 ms	860 KB	Output is correct
37	Correct	3 ms	788 KB	Output is correct
38	Correct	2 ms	860 KB	Output is correct
39	Correct	2 ms	732 KB	Output is correct
40	Correct	3 ms	860 KB	Output is correct
41	Correct	3 ms	848 KB	Output is correct
42	Correct	2 ms	860 KB	Output is correct
43	Correct	2 ms	732 KB	Output is correct
44	Correct	2 ms	860 KB	Output is correct
45	Correct	2 ms	860 KB	Output is correct
46	Correct	4 ms	936 KB	Output is correct
47	Correct	2 ms	860 KB	Output is correct
48	Correct	3 ms	856 KB	Output is correct
49	Correct	3 ms	856 KB	Output is correct
50	Correct	3 ms	848 KB	Output is correct
51	Correct	4 ms	1116 KB	Output is correct

Subtask #4
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	600 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	3 ms	848 KB	Output is correct
28	Correct	3 ms	860 KB	Output is correct
29	Correct	3 ms	856 KB	Output is correct
30	Correct	2 ms	860 KB	Output is correct
31	Correct	2 ms	928 KB	Output is correct
32	Correct	2 ms	860 KB	Output is correct
33	Correct	2 ms	860 KB	Output is correct
34	Correct	2 ms	860 KB	Output is correct
35	Correct	3 ms	856 KB	Output is correct
36	Correct	3 ms	860 KB	Output is correct
37	Correct	3 ms	788 KB	Output is correct
38	Correct	2 ms	860 KB	Output is correct
39	Correct	2 ms	732 KB	Output is correct
40	Correct	3 ms	860 KB	Output is correct
41	Correct	3 ms	848 KB	Output is correct
42	Correct	2 ms	860 KB	Output is correct
43	Correct	2 ms	732 KB	Output is correct
44	Correct	2 ms	860 KB	Output is correct
45	Correct	2 ms	860 KB	Output is correct
46	Correct	4 ms	936 KB	Output is correct
47	Correct	2 ms	860 KB	Output is correct
48	Correct	3 ms	856 KB	Output is correct
49	Correct	3 ms	856 KB	Output is correct
50	Correct	3 ms	848 KB	Output is correct
51	Correct	4 ms	1116 KB	Output is correct
52	Runtime error	31 ms	6228 KB	Execution killed with signal 11
53	Halted	0 ms	0 KB	-

답안 #1008652

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 50.0