oj.uz

Submission #1007026

# Submission time Handle Problem Language Result Execution time Memory
1007026 2024-06-24T10:58:34 Z Unforgettablepl Food Court (JOI21_foodcourt) C++17
7 / 100
 141 ms 14324 KB 
#include <bits/stdc++.h>
using namespace std;

// #define x first
// #define y second

#define int long long

void solve1(int n,int m,int q){
    vector<deque<pair<int,int>>> queues(n+1);
    for(int i=1;i<=q;i++){
        int type;cin>>type;
        if(type==1){
            int l,r,c,k;cin>>l>>r>>c>>k;
            for(int x=l;x<=r;x++)queues[x].emplace_back(k,c);
        } else if(type==2){
            int l,r,k;cin>>l>>r>>k;
            for(int x=l;x<=r;x++){
                int tar = k;
                while(tar and !queues[x].empty()){
                    if(queues[x].front().first<=tar){
                        tar-=queues[x].front().first;
                        queues[x].pop_front();
                    } else {
                        queues[x].front().first-=tar;
                        tar = 0;
                    }
                }
            }
        } else {
            int a,b;cin>>a>>b;
            int curr = 0;
            for(int i=0;i<queues[a].size();i++){
                curr+=queues[a][i].first;
                if(curr>=b){cout<<queues[a][i].second<<'\n';break;}
            }
            if(curr<b)cout<<"0\n";
        }
    }
    exit(0);
}

pair<int,int> tree[524288];

void merge(pair<int,int> &a,pair<int,int> b){
    int cut = min(a.second,b.first);
    a.second-=cut;
    b.first-=cut;
    a.first+=b.first;
    a.second+=b.second;
}
int n;

void update(int qL,int qR,pair<int,int> qu,int x=1,int l=1,int r=n){
    if(qR<l or r<qL)return;
    if(qL<=l and r<=qR){
        merge(tree[x],qu);
        return;
    }
    int mid = (l+r)/2;
    update(qL,qR,qu,2*x,l,mid);
    update(qL,qR,qu,2*x+1,mid+1,r);
}

int get(int qu,int x=1,int l=1,int r=n){
    if(qu<l or r<qu)return 0;
    if(l==r){
        return tree[x].second;
    }
    merge(tree[2*x],tree[x]);
    merge(tree[2*x+1],tree[x]);
    tree[x] = {0,0};
    int mid = (l+r)/2;
    return get(qu,2*x,l,mid)+get(qu,2*x+1,mid+1,r);
}

void solve2(int n,int m,int q){
    for(int i=1;i<=q;i++){
        int type;cin>>type;
        if(type==1){
            int l,r,c,k;cin>>l>>r>>c>>k;
            update(l,r,{0,k});
        } else if(type==2){
            int l,r,k;cin>>l>>r>>k;
            update(l,r,{k,0});
        } else {
            int a,b;cin>>a>>b;
            if(get(a)<b)cout<<"0\n";
            else cout<<"1\n";
        }
    }
    exit(0);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,q;
    cin >> n >> m >> q;
    if(n<=2000 and q<=2000)solve1(n,m,q);
    if(m==1)solve2(n,m,q);
}

Compilation message

foodcourt.cpp: In function 'void solve1(long long int, long long int, long long int)':
foodcourt.cpp:33:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int i=0;i<queues[a].size();i++){
      |                         ~^~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 7 ms 8940 KB Output is correct
4 Correct 10 ms 12636 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 14324 KB Output is correct
8 Correct 11 ms 9820 KB Output is correct
9 Correct 6 ms 2396 KB Output is correct
10 Correct 10 ms 9248 KB Output is correct
11 Correct 8 ms 6592 KB Output is correct
12 Correct 7 ms 2652 KB Output is correct
13 Correct 9 ms 2616 KB Output is correct
14 Correct 13 ms 3692 KB Output is correct
15 Correct 8 ms 4540 KB Output is correct
16 Correct 11 ms 3864 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 5 ms 2140 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 7 ms 8940 KB Output is correct
4 Correct 10 ms 12636 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 14324 KB Output is correct
8 Correct 11 ms 9820 KB Output is correct
9 Correct 6 ms 2396 KB Output is correct
10 Correct 10 ms 9248 KB Output is correct
11 Correct 8 ms 6592 KB Output is correct
12 Correct 7 ms 2652 KB Output is correct
13 Correct 9 ms 2616 KB Output is correct
14 Correct 13 ms 3692 KB Output is correct
15 Correct 8 ms 4540 KB Output is correct
16 Correct 11 ms 3864 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 5 ms 2140 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct
21 Correct 5 ms 2392 KB Output is correct
22 Correct 8 ms 2652 KB Output is correct
23 Correct 9 ms 8644 KB Output is correct
24 Correct 12 ms 12888 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 16 ms 13772 KB Output is correct
28 Correct 13 ms 10588 KB Output is correct
29 Correct 9 ms 4444 KB Output is correct
30 Correct 12 ms 9028 KB Output is correct
31 Correct 11 ms 6420 KB Output is correct
32 Correct 6 ms 2608 KB Output is correct
33 Correct 10 ms 2476 KB Output is correct
34 Correct 14 ms 4924 KB Output is correct
35 Correct 9 ms 2908 KB Output is correct
36 Correct 12 ms 3676 KB Output is correct
37 Correct 1 ms 1372 KB Output is correct
38 Correct 1 ms 1628 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 7 ms 8940 KB Output is correct
4 Correct 10 ms 12636 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 14324 KB Output is correct
8 Correct 11 ms 9820 KB Output is correct
9 Correct 6 ms 2396 KB Output is correct
10 Correct 10 ms 9248 KB Output is correct
11 Correct 8 ms 6592 KB Output is correct
12 Correct 7 ms 2652 KB Output is correct
13 Correct 9 ms 2616 KB Output is correct
14 Correct 13 ms 3692 KB Output is correct
15 Correct 8 ms 4540 KB Output is correct
16 Correct 11 ms 3864 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 5 ms 2140 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 7 ms 8940 KB Output is correct
4 Correct 10 ms 12636 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 14324 KB Output is correct
8 Correct 11 ms 9820 KB Output is correct
9 Correct 6 ms 2396 KB Output is correct
10 Correct 10 ms 9248 KB Output is correct
11 Correct 8 ms 6592 KB Output is correct
12 Correct 7 ms 2652 KB Output is correct
13 Correct 9 ms 2616 KB Output is correct
14 Correct 13 ms 3692 KB Output is correct
15 Correct 8 ms 4540 KB Output is correct
16 Correct 11 ms 3864 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 5 ms 2140 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct
21 Correct 5 ms 2392 KB Output is correct
22 Correct 8 ms 2652 KB Output is correct
23 Correct 9 ms 8644 KB Output is correct
24 Correct 12 ms 12888 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 16 ms 13772 KB Output is correct
28 Correct 13 ms 10588 KB Output is correct
29 Correct 9 ms 4444 KB Output is correct
30 Correct 12 ms 9028 KB Output is correct
31 Correct 11 ms 6420 KB Output is correct
32 Correct 6 ms 2608 KB Output is correct
33 Correct 10 ms 2476 KB Output is correct
34 Correct 14 ms 4924 KB Output is correct
35 Correct 9 ms 2908 KB Output is correct
36 Correct 12 ms 3676 KB Output is correct
37 Correct 1 ms 1372 KB Output is correct
38 Correct 1 ms 1628 KB Output is correct
39 Incorrect 0 ms 348 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 7 ms 8940 KB Output is correct
4 Correct 10 ms 12636 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 14324 KB Output is correct
8 Correct 11 ms 9820 KB Output is correct
9 Correct 6 ms 2396 KB Output is correct
10 Correct 10 ms 9248 KB Output is correct
11 Correct 8 ms 6592 KB Output is correct
12 Correct 7 ms 2652 KB Output is correct
13 Correct 9 ms 2616 KB Output is correct
14 Correct 13 ms 3692 KB Output is correct
15 Correct 8 ms 4540 KB Output is correct
16 Correct 11 ms 3864 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 5 ms 2140 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct
21 Correct 5 ms 2392 KB Output is correct
22 Correct 8 ms 2652 KB Output is correct
23 Correct 9 ms 8644 KB Output is correct
24 Correct 12 ms 12888 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 16 ms 13772 KB Output is correct
28 Correct 13 ms 10588 KB Output is correct
29 Correct 9 ms 4444 KB Output is correct
30 Correct 12 ms 9028 KB Output is correct
31 Correct 11 ms 6420 KB Output is correct
32 Correct 6 ms 2608 KB Output is correct
33 Correct 10 ms 2476 KB Output is correct
34 Correct 14 ms 4924 KB Output is correct
35 Correct 9 ms 2908 KB Output is correct
36 Correct 12 ms 3676 KB Output is correct
37 Correct 1 ms 1372 KB Output is correct
38 Correct 1 ms 1628 KB Output is correct
39 Incorrect 0 ms 348 KB Output isn't correct
40 Halted 0 ms 0 KB -