oj.uz

답안 #348877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348877 2021-01-16T03:33:20 Z ijxjdjd Two Dishes (JOI19_dishes) C++14
0 / 100
 484 ms 96104 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;
const int MAXN = (int)(1e6)+5;
ll A[MAXN];
ll S[MAXN];
ll B[MAXN];
ll T[MAXN];
ll P[MAXN];
ll Q[MAXN];
ll prefA[MAXN];
ll prefB[MAXN];
ll lzy[4*MAXN];
ll mx[4*MAXN];
void push(int n) {
    lzy[2*n] += lzy[n];
    lzy[2*n+1] += lzy[n];
    mx[2*n] += lzy[n];
    mx[2*n+1] += lzy[n];
    lzy[n] = 0;
}
void add(int n, int tl, int tr, int l, int r, ll ad) {
    if (tr < l || r < tl) {
        return;
    }
    if (l <= tl && tr <= r) {
        lzy[n] += ad;
        mx[n] += ad;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        add(2*n, tl, tm, l, r, ad);
        add(2*n+1, tm+1, tr, l, r, ad);
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
ll query(int n, int tl, int tr, int l, int r) {
   if (tr < l || r < tl) {
        return ll(-1e18);
    }
    if (l <= tl && tr <= r) {
        return mx[n];
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        return max(query(2*n, tl, tm, l, r), query(2*n+1, tm+1, tr, l, r));
    }
}
void upd(int n, int tl, int tr, int i, ll val) {
    if (tl == tr) {
        mx[n] = max(mx[n], val);
        lzy[n] = 0;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        if (i <= tm) {
            upd(2*n, tl, tm, i, val);
        }
        else {
            upd(2*n+1, tm+1, tr, i, val);
        }
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
vector<pair<int, ll>> row[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	FR(i, 4*MAXN) {
        mx[i] = (ll)(-1e18);
	}
	for (int i = 1; i <= N; i++) {
        cin >> A[i] >> S[i] >> P[i];
        prefA[i] = A[i] + prefA[i-1];
	}
	for (int i = 1; i <= M; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        prefB[i] = B[i] + prefB[i-1];
	}
	ll offset = 0;
	for (int i = 1; i <= N; i++) {
        if (prefA[i] <= S[i]) {
            int low = 0;
            int high = M;
            ll g = S[i] - prefA[i];
            while (low < high) {
                int mid = (low + high+1)/2;
                if (prefB[mid] <= g) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            row[i].push_back({low, P[i]});
        }
	}
	for (int i = 1; i <= M; i++) {
        if (prefB[i] <= T[i]) {
            int low = 0;
            int high = N;
            ll g = T[i] - prefB[i];
            while (low < high) {
                int mid = (low + high+1)/2;
                if (prefA[mid] <= g) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            offset += Q[i];
            row[low+1].push_back({i-1, -Q[i]});
        }
	}
	upd(1, 0, N, 0, 0);
	FR(i, N+2) {
        sort(row[i].begin(), row[i].end());
        while (row[i].size()) {
            while (row[i].size() != 1) {
                if (row[i][row[i].size()-1].first == row[i][row[i].size()-2].first) {
                    row[i][row[i].size()-2].second += row[i][row[i].size()-1].second;
                    row[i].pop_back();
                }
                else {
                    break;
                }
            }
            upd(1, 0, N, row[i].back().first+1, query(1, 0, N, 0, row[i].back().first));
            add(1, 0, N, 0, row[i].back().first, row[i].back().second);
            row[i].pop_back();
        }
	}
	cout << mx[1] + offset;
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 94956 KB Output is correct
2 Correct 474 ms 96104 KB Output is correct
3 Correct 438 ms 94804 KB Output is correct
4 Correct 343 ms 89836 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 484 ms 94948 KB Output is correct
7 Incorrect 137 ms 72548 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 33 ms 55168 KB Output is correct
4 Correct 36 ms 55148 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 35 ms 55148 KB Output is correct
8 Correct 32 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 33 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Incorrect 34 ms 55148 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 33 ms 55168 KB Output is correct
4 Correct 36 ms 55148 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 35 ms 55148 KB Output is correct
8 Correct 32 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 33 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Incorrect 34 ms 55148 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 33 ms 55168 KB Output is correct
4 Correct 36 ms 55148 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 35 ms 55148 KB Output is correct
8 Correct 32 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 33 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Incorrect 34 ms 55148 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 33 ms 55168 KB Output is correct
4 Correct 36 ms 55148 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 35 ms 55148 KB Output is correct
8 Correct 32 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 33 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Incorrect 34 ms 55148 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 33 ms 55168 KB Output is correct
4 Correct 36 ms 55148 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 35 ms 55148 KB Output is correct
8 Correct 32 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 33 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Incorrect 34 ms 55148 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 94956 KB Output is correct
2 Correct 474 ms 96104 KB Output is correct
3 Correct 438 ms 94804 KB Output is correct
4 Correct 343 ms 89836 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 484 ms 94948 KB Output is correct
7 Incorrect 137 ms 72548 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 94956 KB Output is correct
2 Correct 474 ms 96104 KB Output is correct
3 Correct 438 ms 94804 KB Output is correct
4 Correct 343 ms 89836 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 484 ms 94948 KB Output is correct
7 Incorrect 137 ms 72548 KB Output isn't correct
8 Halted 0 ms 0 KB -