oj.uz

Submission #797286

# Submission time Handle Problem Language Result Execution time Memory
797286 2023-07-29T08:49:27 Z vjudge1 Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 236032 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{
    ll 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;
    l = r = x = y = 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:119: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]
  119 |             if(d[x].size() >= y)
      |                ~~~~~~~~~~~~^~~~
foodcourt.cpp:133:29: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  133 |                 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 56344 KB Output is correct
2 Correct 50 ms 63400 KB Output is correct
3 Correct 47 ms 66892 KB Output is correct
4 Correct 61 ms 79556 KB Output is correct
5 Correct 38 ms 49116 KB Output is correct
6 Correct 29 ms 49144 KB Output is correct
7 Correct 52 ms 71888 KB Output is correct
8 Correct 50 ms 71360 KB Output is correct
9 Correct 52 ms 71372 KB Output is correct
10 Correct 53 ms 72480 KB Output is correct
11 Correct 53 ms 73088 KB Output is correct
12 Correct 52 ms 72028 KB Output is correct
13 Correct 72 ms 82632 KB Output is correct
14 Correct 69 ms 90540 KB Output is correct
15 Correct 54 ms 71796 KB Output is correct
16 Correct 68 ms 90044 KB Output is correct
17 Correct 41 ms 60624 KB Output is correct
18 Correct 51 ms 67600 KB Output is correct
19 Correct 27 ms 49344 KB Output is correct
20 Correct 27 ms 49364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56344 KB Output is correct
2 Correct 50 ms 63400 KB Output is correct
3 Correct 47 ms 66892 KB Output is correct
4 Correct 61 ms 79556 KB Output is correct
5 Correct 38 ms 49116 KB Output is correct
6 Correct 29 ms 49144 KB Output is correct
7 Correct 52 ms 71888 KB Output is correct
8 Correct 50 ms 71360 KB Output is correct
9 Correct 52 ms 71372 KB Output is correct
10 Correct 53 ms 72480 KB Output is correct
11 Correct 53 ms 73088 KB Output is correct
12 Correct 52 ms 72028 KB Output is correct
13 Correct 72 ms 82632 KB Output is correct
14 Correct 69 ms 90540 KB Output is correct
15 Correct 54 ms 71796 KB Output is correct
16 Correct 68 ms 90044 KB Output is correct
17 Correct 41 ms 60624 KB Output is correct
18 Correct 51 ms 67600 KB Output is correct
19 Correct 27 ms 49344 KB Output is correct
20 Correct 27 ms 49364 KB Output is correct
21 Correct 41 ms 61976 KB Output is correct
22 Correct 42 ms 63256 KB Output is correct
23 Correct 51 ms 68604 KB Output is correct
24 Correct 59 ms 79576 KB Output is correct
25 Correct 29 ms 49120 KB Output is correct
26 Correct 28 ms 49108 KB Output is correct
27 Correct 59 ms 68920 KB Output is correct
28 Correct 54 ms 72436 KB Output is correct
29 Correct 52 ms 72196 KB Output is correct
30 Correct 51 ms 71668 KB Output is correct
31 Correct 49 ms 68468 KB Output is correct
32 Correct 49 ms 68300 KB Output is correct
33 Correct 58 ms 81308 KB Output is correct
34 Correct 68 ms 90332 KB Output is correct
35 Correct 61 ms 78964 KB Output is correct
36 Correct 68 ms 89916 KB Output is correct
37 Correct 27 ms 49236 KB Output is correct
38 Correct 27 ms 49368 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 51812 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 125 ms 117736 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 56344 KB Output is correct
2 Correct 50 ms 63400 KB Output is correct
3 Correct 47 ms 66892 KB Output is correct
4 Correct 61 ms 79556 KB Output is correct
5 Correct 38 ms 49116 KB Output is correct
6 Correct 29 ms 49144 KB Output is correct
7 Correct 52 ms 71888 KB Output is correct
8 Correct 50 ms 71360 KB Output is correct
9 Correct 52 ms 71372 KB Output is correct
10 Correct 53 ms 72480 KB Output is correct
11 Correct 53 ms 73088 KB Output is correct
12 Correct 52 ms 72028 KB Output is correct
13 Correct 72 ms 82632 KB Output is correct
14 Correct 69 ms 90540 KB Output is correct
15 Correct 54 ms 71796 KB Output is correct
16 Correct 68 ms 90044 KB Output is correct
17 Correct 41 ms 60624 KB Output is correct
18 Correct 51 ms 67600 KB Output is correct
19 Correct 27 ms 49344 KB Output is correct
20 Correct 27 ms 49364 KB Output is correct
21 Incorrect 63 ms 51812 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 1069 ms 236032 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 56344 KB Output is correct
2 Correct 50 ms 63400 KB Output is correct
3 Correct 47 ms 66892 KB Output is correct
4 Correct 61 ms 79556 KB Output is correct
5 Correct 38 ms 49116 KB Output is correct
6 Correct 29 ms 49144 KB Output is correct
7 Correct 52 ms 71888 KB Output is correct
8 Correct 50 ms 71360 KB Output is correct
9 Correct 52 ms 71372 KB Output is correct
10 Correct 53 ms 72480 KB Output is correct
11 Correct 53 ms 73088 KB Output is correct
12 Correct 52 ms 72028 KB Output is correct
13 Correct 72 ms 82632 KB Output is correct
14 Correct 69 ms 90540 KB Output is correct
15 Correct 54 ms 71796 KB Output is correct
16 Correct 68 ms 90044 KB Output is correct
17 Correct 41 ms 60624 KB Output is correct
18 Correct 51 ms 67600 KB Output is correct
19 Correct 27 ms 49344 KB Output is correct
20 Correct 27 ms 49364 KB Output is correct
21 Correct 41 ms 61976 KB Output is correct
22 Correct 42 ms 63256 KB Output is correct
23 Correct 51 ms 68604 KB Output is correct
24 Correct 59 ms 79576 KB Output is correct
25 Correct 29 ms 49120 KB Output is correct
26 Correct 28 ms 49108 KB Output is correct
27 Correct 59 ms 68920 KB Output is correct
28 Correct 54 ms 72436 KB Output is correct
29 Correct 52 ms 72196 KB Output is correct
30 Correct 51 ms 71668 KB Output is correct
31 Correct 49 ms 68468 KB Output is correct
32 Correct 49 ms 68300 KB Output is correct
33 Correct 58 ms 81308 KB Output is correct
34 Correct 68 ms 90332 KB Output is correct
35 Correct 61 ms 78964 KB Output is correct
36 Correct 68 ms 89916 KB Output is correct
37 Correct 27 ms 49236 KB Output is correct
38 Correct 27 ms 49368 KB Output is correct
39 Incorrect 63 ms 51812 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 56344 KB Output is correct
2 Correct 50 ms 63400 KB Output is correct
3 Correct 47 ms 66892 KB Output is correct
4 Correct 61 ms 79556 KB Output is correct
5 Correct 38 ms 49116 KB Output is correct
6 Correct 29 ms 49144 KB Output is correct
7 Correct 52 ms 71888 KB Output is correct
8 Correct 50 ms 71360 KB Output is correct
9 Correct 52 ms 71372 KB Output is correct
10 Correct 53 ms 72480 KB Output is correct
11 Correct 53 ms 73088 KB Output is correct
12 Correct 52 ms 72028 KB Output is correct
13 Correct 72 ms 82632 KB Output is correct
14 Correct 69 ms 90540 KB Output is correct
15 Correct 54 ms 71796 KB Output is correct
16 Correct 68 ms 90044 KB Output is correct
17 Correct 41 ms 60624 KB Output is correct
18 Correct 51 ms 67600 KB Output is correct
19 Correct 27 ms 49344 KB Output is correct
20 Correct 27 ms 49364 KB Output is correct
21 Correct 41 ms 61976 KB Output is correct
22 Correct 42 ms 63256 KB Output is correct
23 Correct 51 ms 68604 KB Output is correct
24 Correct 59 ms 79576 KB Output is correct
25 Correct 29 ms 49120 KB Output is correct
26 Correct 28 ms 49108 KB Output is correct
27 Correct 59 ms 68920 KB Output is correct
28 Correct 54 ms 72436 KB Output is correct
29 Correct 52 ms 72196 KB Output is correct
30 Correct 51 ms 71668 KB Output is correct
31 Correct 49 ms 68468 KB Output is correct
32 Correct 49 ms 68300 KB Output is correct
33 Correct 58 ms 81308 KB Output is correct
34 Correct 68 ms 90332 KB Output is correct
35 Correct 61 ms 78964 KB Output is correct
36 Correct 68 ms 89916 KB Output is correct
37 Correct 27 ms 49236 KB Output is correct
38 Correct 27 ms 49368 KB Output is correct
39 Incorrect 63 ms 51812 KB Output isn't correct
40 Halted 0 ms 0 KB -