oj.uz

Submission #797278

# Submission time Handle Problem Language Result Execution time Memory
797278 2023-07-29T08:45:32 Z vjudge1 Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 206456 KB 

// Author : حسن

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 7e4 + 9 , mod = 1e9 + 7;
ll  a[N] = {},  c[N] , dp[N] = {} , b[N];
deque<ll>d[N];
vector<pair<ll,ll>>v[N];
struct qu{
    int k , l, r , x , y;
};
void solve(){
    ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
    cin>>n>>m>>q;
    set<ll>st;
    if(n <= 2000 && q <= 2000){
    while(q--){
        cin>>k;
        if(k == 1){
            cin>>l>>r>>x>>y;
            for(i = l; i <=r ;i++){
                v[i].pb({y , x}) , b[i] += y;
                if(d[i].size() == 0)
                d[i].pb(y);
                else
                    d[i].pb(d[i].back() + y);
            }
        }else if(k == 2){
            cin>>l>>r>>x;
                for(i = l; i <= r; i++){
                    c[i] += x;
                    if(b[i]  < c[i])
                        c[i] = b[i];
                }
        }else{
            cin>>x>>y;
            if(b[x] - c[x] >= y){
                k = c[x] + y;
                l = 0;
                r = v[x].size() - 1;
                while(l != r){
                    m = (l + r) / 2;
                    if(d[x][m] >= k)
                        r = m ;
                    else
                        l = m + 1;
                }
                cout<<v[x][l].se<<"\n";
            }else {
            cout<<0<<"\n";
            }
        }
    }
    return;
    }
    vector<qu>vc;
    f = 0;
    while(q--){
        cin>>k;
        if(k == 1){
            cin>>l>>r>>x>>y;
            vc.pb({k , l , r , x, y });
            if(y != 1)
                f = 1;
        }else if(k == 2){
            cin>>l>>r>>x;
            if(x != 1)
                f = 1;
            vc.pb({k , l , r , x, y });
        }else{
            cin>>x>>y;
            vc.pb({k , l , r , x, y });
        }
    }
    z = 0;
    for(auto to : vc){
        k = to.k , l = to.l , r = to.r , x = to.x , y = to.x;
        if(f == 1 || f == 0){
        if(k == 1){
            for(i = l; i <=r ;i++)
                d[i].pb(x) , st.insert(i);
        }else if(k == 2){
            auto it = st.lower_bound(l);
            while(st.size() && it != st.end() && *it <= r){
            i = *it;
            s = 0;
            while(d[i].size() && s < x){
                d[i].pop_front();
                s++;
            }
            if(d[i].size() == 0)
                st.erase(i);
            it = st.lower_bound(i + 1);
            }
        }else{
            if(d[x].size() >= y)
                cout<<d[x][y - 1]<<"\n";
            else
                cout<<0<<"\n";
        }
        }else {
            if(k == 3){
                deque<int>v;
                for(i = 0; i < z; i++){
                    if(vc[i].k == 1 && vc[i].l <= x && vc[i].r >= x)
                        v.pb(vc[i].x);
                    if(vc[i].k == 2 && vc[i].l <= x && vc[i].r >= x && v.size())
                        v.pop_front();
                }
                if(v.size() >= y)
                    cout<<v[y - 1]<<"\n";
                else
                    cout<<0<<"\n";
            }
        }
        z++;
    }
}

int main(){

     TL;/*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */

int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message

foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:84:20: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
   84 |             vc.pb({k , l , r , x, y });
      |                    ^
foodcourt.cpp:84:24: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
   84 |             vc.pb({k , l , r , x, y });
      |                        ^
foodcourt.cpp:84:28: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   84 |             vc.pb({k , l , r , x, y });
      |                            ^
foodcourt.cpp:84:32: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   84 |             vc.pb({k , l , r , x, y });
      |                                ^
foodcourt.cpp:84:35: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   84 |             vc.pb({k , l , r , x, y });
      |                                   ^
foodcourt.cpp:91:20: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
   91 |             vc.pb({k , l , r , x, y });
      |                    ^
foodcourt.cpp:91:24: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
   91 |             vc.pb({k , l , r , x, y });
      |                        ^
foodcourt.cpp:91:28: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   91 |             vc.pb({k , l , r , x, y });
      |                            ^
foodcourt.cpp:91:32: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   91 |             vc.pb({k , l , r , x, y });
      |                                ^
foodcourt.cpp:91:35: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   91 |             vc.pb({k , l , r , x, y });
      |                                   ^
foodcourt.cpp:94:20: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
   94 |             vc.pb({k , l , r , x, y });
      |                    ^
foodcourt.cpp:94:24: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
   94 |             vc.pb({k , l , r , x, y });
      |                        ^
foodcourt.cpp:94:28: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   94 |             vc.pb({k , l , r , x, y });
      |                            ^
foodcourt.cpp:94:32: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   94 |             vc.pb({k , l , r , x, y });
      |                                ^
foodcourt.cpp:94:35: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   94 |             vc.pb({k , l , r , x, y });
      |                                   ^
foodcourt.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  118 |             if(d[x].size() >= y)
      |                ~~~~~~~~~~~~^~~~
foodcourt.cpp:132:29: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  132 |                 if(v.size() >= y)
      |                    ~~~~~~~~~^~~~
foodcourt.cpp:35:16: warning: unused variable 'j' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                ^
foodcourt.cpp:35:61: warning: unused variable 'mn' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                             ^~
foodcourt.cpp:35:74: warning: unused variable 'mx' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                                          ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56396 KB Output is correct
2 Correct 40 ms 63372 KB Output is correct
3 Correct 43 ms 66896 KB Output is correct
4 Correct 56 ms 79544 KB Output is correct
5 Correct 28 ms 49048 KB Output is correct
6 Correct 34 ms 49108 KB Output is correct
7 Correct 57 ms 71868 KB Output is correct
8 Correct 50 ms 71396 KB Output is correct
9 Correct 48 ms 71364 KB Output is correct
10 Correct 48 ms 72508 KB Output is correct
11 Correct 49 ms 73044 KB Output is correct
12 Correct 59 ms 72048 KB Output is correct
13 Correct 64 ms 82644 KB Output is correct
14 Correct 67 ms 90552 KB Output is correct
15 Correct 51 ms 71876 KB Output is correct
16 Correct 66 ms 90016 KB Output is correct
17 Correct 38 ms 60664 KB Output is correct
18 Correct 50 ms 67528 KB Output is correct
19 Correct 27 ms 49336 KB Output is correct
20 Correct 27 ms 49312 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56396 KB Output is correct
2 Correct 40 ms 63372 KB Output is correct
3 Correct 43 ms 66896 KB Output is correct
4 Correct 56 ms 79544 KB Output is correct
5 Correct 28 ms 49048 KB Output is correct
6 Correct 34 ms 49108 KB Output is correct
7 Correct 57 ms 71868 KB Output is correct
8 Correct 50 ms 71396 KB Output is correct
9 Correct 48 ms 71364 KB Output is correct
10 Correct 48 ms 72508 KB Output is correct
11 Correct 49 ms 73044 KB Output is correct
12 Correct 59 ms 72048 KB Output is correct
13 Correct 64 ms 82644 KB Output is correct
14 Correct 67 ms 90552 KB Output is correct
15 Correct 51 ms 71876 KB Output is correct
16 Correct 66 ms 90016 KB Output is correct
17 Correct 38 ms 60664 KB Output is correct
18 Correct 50 ms 67528 KB Output is correct
19 Correct 27 ms 49336 KB Output is correct
20 Correct 27 ms 49312 KB Output is correct
21 Correct 40 ms 62028 KB Output is correct
22 Correct 51 ms 63312 KB Output is correct
23 Correct 47 ms 68684 KB Output is correct
24 Correct 62 ms 79536 KB Output is correct
25 Correct 26 ms 49024 KB Output is correct
26 Correct 29 ms 49032 KB Output is correct
27 Correct 47 ms 68940 KB Output is correct
28 Correct 50 ms 72488 KB Output is correct
29 Correct 50 ms 72120 KB Output is correct
30 Correct 50 ms 71724 KB Output is correct
31 Correct 50 ms 68560 KB Output is correct
32 Correct 46 ms 68336 KB Output is correct
33 Correct 67 ms 81320 KB Output is correct
34 Correct 68 ms 90444 KB Output is correct
35 Correct 53 ms 78928 KB Output is correct
36 Correct 67 ms 89828 KB Output is correct
37 Correct 27 ms 49324 KB Output is correct
38 Correct 24 ms 49328 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 108700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56396 KB Output is correct
2 Correct 40 ms 63372 KB Output is correct
3 Correct 43 ms 66896 KB Output is correct
4 Correct 56 ms 79544 KB Output is correct
5 Correct 28 ms 49048 KB Output is correct
6 Correct 34 ms 49108 KB Output is correct
7 Correct 57 ms 71868 KB Output is correct
8 Correct 50 ms 71396 KB Output is correct
9 Correct 48 ms 71364 KB Output is correct
10 Correct 48 ms 72508 KB Output is correct
11 Correct 49 ms 73044 KB Output is correct
12 Correct 59 ms 72048 KB Output is correct
13 Correct 64 ms 82644 KB Output is correct
14 Correct 67 ms 90552 KB Output is correct
15 Correct 51 ms 71876 KB Output is correct
16 Correct 66 ms 90016 KB Output is correct
17 Correct 38 ms 60664 KB Output is correct
18 Correct 50 ms 67528 KB Output is correct
19 Correct 27 ms 49336 KB Output is correct
20 Correct 27 ms 49312 KB Output is correct
21 Incorrect 59 ms 50532 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 206456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56396 KB Output is correct
2 Correct 40 ms 63372 KB Output is correct
3 Correct 43 ms 66896 KB Output is correct
4 Correct 56 ms 79544 KB Output is correct
5 Correct 28 ms 49048 KB Output is correct
6 Correct 34 ms 49108 KB Output is correct
7 Correct 57 ms 71868 KB Output is correct
8 Correct 50 ms 71396 KB Output is correct
9 Correct 48 ms 71364 KB Output is correct
10 Correct 48 ms 72508 KB Output is correct
11 Correct 49 ms 73044 KB Output is correct
12 Correct 59 ms 72048 KB Output is correct
13 Correct 64 ms 82644 KB Output is correct
14 Correct 67 ms 90552 KB Output is correct
15 Correct 51 ms 71876 KB Output is correct
16 Correct 66 ms 90016 KB Output is correct
17 Correct 38 ms 60664 KB Output is correct
18 Correct 50 ms 67528 KB Output is correct
19 Correct 27 ms 49336 KB Output is correct
20 Correct 27 ms 49312 KB Output is correct
21 Correct 40 ms 62028 KB Output is correct
22 Correct 51 ms 63312 KB Output is correct
23 Correct 47 ms 68684 KB Output is correct
24 Correct 62 ms 79536 KB Output is correct
25 Correct 26 ms 49024 KB Output is correct
26 Correct 29 ms 49032 KB Output is correct
27 Correct 47 ms 68940 KB Output is correct
28 Correct 50 ms 72488 KB Output is correct
29 Correct 50 ms 72120 KB Output is correct
30 Correct 50 ms 71724 KB Output is correct
31 Correct 50 ms 68560 KB Output is correct
32 Correct 46 ms 68336 KB Output is correct
33 Correct 67 ms 81320 KB Output is correct
34 Correct 68 ms 90444 KB Output is correct
35 Correct 53 ms 78928 KB Output is correct
36 Correct 67 ms 89828 KB Output is correct
37 Correct 27 ms 49324 KB Output is correct
38 Correct 24 ms 49328 KB Output is correct
39 Incorrect 59 ms 50532 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56396 KB Output is correct
2 Correct 40 ms 63372 KB Output is correct
3 Correct 43 ms 66896 KB Output is correct
4 Correct 56 ms 79544 KB Output is correct
5 Correct 28 ms 49048 KB Output is correct
6 Correct 34 ms 49108 KB Output is correct
7 Correct 57 ms 71868 KB Output is correct
8 Correct 50 ms 71396 KB Output is correct
9 Correct 48 ms 71364 KB Output is correct
10 Correct 48 ms 72508 KB Output is correct
11 Correct 49 ms 73044 KB Output is correct
12 Correct 59 ms 72048 KB Output is correct
13 Correct 64 ms 82644 KB Output is correct
14 Correct 67 ms 90552 KB Output is correct
15 Correct 51 ms 71876 KB Output is correct
16 Correct 66 ms 90016 KB Output is correct
17 Correct 38 ms 60664 KB Output is correct
18 Correct 50 ms 67528 KB Output is correct
19 Correct 27 ms 49336 KB Output is correct
20 Correct 27 ms 49312 KB Output is correct
21 Correct 40 ms 62028 KB Output is correct
22 Correct 51 ms 63312 KB Output is correct
23 Correct 47 ms 68684 KB Output is correct
24 Correct 62 ms 79536 KB Output is correct
25 Correct 26 ms 49024 KB Output is correct
26 Correct 29 ms 49032 KB Output is correct
27 Correct 47 ms 68940 KB Output is correct
28 Correct 50 ms 72488 KB Output is correct
29 Correct 50 ms 72120 KB Output is correct
30 Correct 50 ms 71724 KB Output is correct
31 Correct 50 ms 68560 KB Output is correct
32 Correct 46 ms 68336 KB Output is correct
33 Correct 67 ms 81320 KB Output is correct
34 Correct 68 ms 90444 KB Output is correct
35 Correct 53 ms 78928 KB Output is correct
36 Correct 67 ms 89828 KB Output is correct
37 Correct 27 ms 49324 KB Output is correct
38 Correct 24 ms 49328 KB Output is correct
39 Incorrect 59 ms 50532 KB Output isn't correct
40 Halted 0 ms 0 KB -