oj.uz

답안 #878650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878650 2023-11-25T03:27:46 Z thangdz2k7 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 344 ms 56196 KB 
#include <bits/stdc++.h>
#define ll pair <long long, long long>
#define ii pair <int, long long>
#define F first
#define S second
#define pb push_back
#define ill long long
 
using namespace std;
 
const int N = 2e5 + 5e4 + 5;
 
int n, m, q, group[N], ans[N];
vector <ii> event[N], numadd[N], query[N];
 
long long cur[4 * N], Min[4 * N];
 
void update_cur(int s, int l, int r, int u, ill val){
    if (l == r){
        cur[s] += val;
        Min[s] = min(0ll, cur[s]);
        return;
    }
 
    int mid = l + r >> 1;
    if (mid >= u) update_cur(2 * s, l, mid, u, val);
    else update_cur(2 * s + 1, mid + 1, r, u, val);
 
    cur[s] = cur[2 * s] + cur[2 * s + 1];
    Min[s] = min(Min[2 * s], cur[2 * s] + Min[2 * s + 1]);
}
 
ll get_cur(int s, int l, int r, int u){
    if (l > u) return ll(0, 0);
    if (r <= u) return ll(cur[s], Min[s]);
 
    int mid = l + r >> 1;
    ll A = get_cur(2 * s, l, mid, u);
    ll B = get_cur(2 * s + 1, mid + 1, r, u);
 
    return ll(A.F + B.F, min(A.S, A.F + B.S));
}
 
long long sumadd[4 * N];
 
void update_sumadd(int s, int l, int r, int u, ill val){
    if (l == r){
        sumadd[s] += val;
        return;
    }
 
    int mid = l + r >> 1;
    if (mid >= u) update_sumadd(2 * s, l, mid, u, val);
    else update_sumadd(2 * s + 1, mid + 1, r, u, val);
    sumadd[s] = sumadd[2 * s] + sumadd[2 * s + 1];
}
 
long long get_sumadd(int s, int l, int r, int u){
    if (l > u) return 0;
    if (r <= u) return sumadd[s];
 
    int mid = l + r >> 1;
    return get_sumadd(2 * s, l, mid, u) + get_sumadd(2 * s + 1, mid + 1, r, u);
}
 
int get_pos(int s, int l, int r, long long val){
    if (l == r) return l;
    int mid = l + r >> 1;
    if (sumadd[2 * s] < val) return get_pos(2 * s + 1, mid + 1, r, val - sumadd[2 * s]);
    return get_pos(2 * s, l, mid, val);
}
 
void solve(){
    cin >> n >> m >> q;
    for (int i = 1; i <= q; ++ i){
        ans[i] = -1;
        int t; cin >> t;
        if (t == 1){
            int l, r, k; cin >> l >> r >> group[i] >> k;
            event[l].pb(ii(i, k));
            event[r + 1].pb(ii(i, -k));
            numadd[l].pb(ii(i, k));
            numadd[r + 1].pb(ii(i, -k));
        }
        if (t == 2){
            int l, r, k; cin >> l >> r >> k;
            event[l].pb(ii(i, -k));
            event[r + 1].pb(ii(i, k));
        }
        if (t == 3){
            int a;
            ill b; cin >> a >> b;
            query[a].pb(ii(i, b));
        }
    }
 
    for (int i = 1; i <= n; ++ i){
        for (ii v : event[i]) {
            update_cur(1, 1, q, v.F, v.S);
            //cout << i << ' ' << v.F << ' ' << v.S << endl;
        }
        for (ii v : numadd[i]) update_sumadd(1, 1, q, v.F, v.S);
        for (ii v : query[i]){
            long long num_cur = get_cur(1, 1, q, v.F).S;
            //cout << gnum_cur.F << ' ' << gnum_cur.S << endl;
            if (num_cur < v.S) ans[v.F] = 0;
            else ans[v.F] = group[get_pos(1, 1, q, num_cur + v.S)];
        }
    }
 
    for (int i = 1; i <= q; ++ i) if (ans[i] >= 0) cout << ans[i] << '\n';
}
 
signed main(){
    //freopen("foodcourt.inp", "r", stdin);
    //freopen("foodcourt.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
 
    return 0;
}

Compilation message

foodcourt.cpp: In function 'void update_cur(int, int, int, int, long long int)':
foodcourt.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'std::pair<long long int, long long int> get_cur(int, int, int, int)':
foodcourt.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'void update_sumadd(int, int, int, int, long long int)':
foodcourt.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'long long int get_sumadd(int, int, int, int)':
foodcourt.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'int get_pos(int, int, int, long long int)':
foodcourt.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 31972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 344 ms 56196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 28948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -