oj.uz

Submission #682286

# Submission time Handle Problem Language Result Execution time Memory
682286 2023-01-16T05:45:23 Z vjudge1 Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;

// #define ORD_SET
// #define ROPE
#ifdef ORD_SET
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    template<typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#ifdef ROPE
    #include <ext/rope>
    using namespace __gnu_cxx;
#endif        

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define ll int
void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
void NotInteractive() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
void pre(ll a) { cout<<fixed<<setprecision(a); }
ll bit(ll x) { return __builtin_popcountll(x); }
ll binpow(ll x, ll y, ll z) { ll pow = 1; while(y) { if(y&1) pow *= x, pow %= z; x *= x, x %= z; y >>= 1; } return pow; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct sn { ll l, r, x; }; // a.swap(b)
ll B = 316;
const ll mod = (ll)1e9+7;
const ll inf = (ll)1e18+7;
const ll MX = LLONG_MAX;
const ll MN = LLONG_MIN;
const ld P = acos(-1.0);
const ll N = (ll)3e5+5;
vector<pair<ll, ll>> v[N];
vector<ll> len(N);
ll t[N], l[N], r[N], c[N], k[N];

void kigash() {
    ll n, m, q;
    cin>>n>>m>>q;
    for(ll i=1; i<=q; i++) {
        ll tmp = -1, lmp = -1, rmp = -1, cmp = -1, kmp = -1;
        cin>>tmp;
        if(tmp==1) cin>>lmp>>rmp>>cmp>>kmp;
        else if(tmp==2) cin>>lmp>>rmp>>kmp;
        else cin>>cmp>>kmp;
        t[i] = tmp, l[i] = lmp, r[i] = rmp, c[i] = cmp, k[i] = kmp;
    }
    for(ll tt=1; tt<=q; tt++) {
        // if(tt==3) {
        //     for(ll i=1; i<=n; i++) {
        //         for(auto x: v[i]) cout<<x.ff<<" "<<x.ss<<"\n";
        //         cout<<"\n";
        //     }
        //     return;
        // }
        if(t[tt]==1) {
            for(ll i=l[tt]; i<=r[tt]; i++) v[i].pb({k[tt], c[tt]}), len[i] += k[tt];
        }
        else if(t[tt]==2) {
            for(ll i=l[tt]; i<=r[tt]; i++) {
                if(len[i]<=k[tt]) len[i] = 0, v[i].clear();
                else {
                    vector<pair<ll, ll>> tmp;
                    ll f = 0;
                    len[i] -= k[tt];
                    for(ll j=0, sum = 0; j<sz(v[i]); j++) {
                        if(f) {
                            tmp.pb(v[i][j]);
                            continue;
                        }
                        sum += v[i][j].ff;
                        if(sum==k[tt]) f = 1;
                        else if(sum>k[tt]) {
                            tmp.pb({v[i][j].ff-(k[tt]-sum+v[i][j].ff), v[i][j].ss});
                            f = 1;
                        }
                    }
                    v[i] = tmp;
                }
            }
        }
        else {
            if(len[c[tt]]>=k[tt]) {
                for(ll i=0, sum = 0; i<sz(v[c[tt]]); i++) {
                    sum += v[c[tt]][i].ff;
                    if(sum>=k[tt]) {
                        cout<<v[c[tt]][i].ss<<"\n";
                        break;
                    }
                }
            }
            else cout<<"0\n";
        }
    }
    return;
}

signed main(/**/) {
    // freopen("");
    NotInteractive();
    // precalc();
    
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) kigash();
    
    exit(0);
}

Compilation message

foodcourt.cpp: In function 'void freopen(std::string)':
foodcourt.cpp:31:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:31:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10452 KB Output is correct
2 Correct 89 ms 10992 KB Output is correct
3 Correct 160 ms 21108 KB Output is correct
4 Correct 403 ms 24780 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 952 ms 27356 KB Output is correct
8 Correct 668 ms 22284 KB Output is correct
9 Correct 162 ms 11316 KB Output is correct
10 Correct 576 ms 21824 KB Output is correct
11 Correct 390 ms 16796 KB Output is correct
12 Correct 140 ms 11276 KB Output is correct
13 Correct 184 ms 10788 KB Output is correct
14 Correct 222 ms 13848 KB Output is correct
15 Correct 306 ms 13724 KB Output is correct
16 Correct 188 ms 11812 KB Output is correct
17 Correct 45 ms 10324 KB Output is correct
18 Correct 86 ms 10716 KB Output is correct
19 Correct 8 ms 9940 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10452 KB Output is correct
2 Correct 89 ms 10992 KB Output is correct
3 Correct 160 ms 21108 KB Output is correct
4 Correct 403 ms 24780 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 952 ms 27356 KB Output is correct
8 Correct 668 ms 22284 KB Output is correct
9 Correct 162 ms 11316 KB Output is correct
10 Correct 576 ms 21824 KB Output is correct
11 Correct 390 ms 16796 KB Output is correct
12 Correct 140 ms 11276 KB Output is correct
13 Correct 184 ms 10788 KB Output is correct
14 Correct 222 ms 13848 KB Output is correct
15 Correct 306 ms 13724 KB Output is correct
16 Correct 188 ms 11812 KB Output is correct
17 Correct 45 ms 10324 KB Output is correct
18 Correct 86 ms 10716 KB Output is correct
19 Correct 8 ms 9940 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Correct 55 ms 10884 KB Output is correct
22 Correct 100 ms 11432 KB Output is correct
23 Correct 238 ms 20036 KB Output is correct
24 Correct 346 ms 24632 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 6 ms 9848 KB Output is correct
27 Correct 896 ms 24676 KB Output is correct
28 Correct 784 ms 22940 KB Output is correct
29 Correct 210 ms 13644 KB Output is correct
30 Correct 544 ms 21320 KB Output is correct
31 Correct 383 ms 16360 KB Output is correct
32 Correct 107 ms 11144 KB Output is correct
33 Correct 134 ms 10644 KB Output is correct
34 Correct 373 ms 13860 KB Output is correct
35 Correct 238 ms 11440 KB Output is correct
36 Correct 191 ms 11960 KB Output is correct
37 Correct 7 ms 9876 KB Output is correct
38 Correct 7 ms 10000 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10452 KB Output is correct
2 Correct 89 ms 10992 KB Output is correct
3 Correct 160 ms 21108 KB Output is correct
4 Correct 403 ms 24780 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 952 ms 27356 KB Output is correct
8 Correct 668 ms 22284 KB Output is correct
9 Correct 162 ms 11316 KB Output is correct
10 Correct 576 ms 21824 KB Output is correct
11 Correct 390 ms 16796 KB Output is correct
12 Correct 140 ms 11276 KB Output is correct
13 Correct 184 ms 10788 KB Output is correct
14 Correct 222 ms 13848 KB Output is correct
15 Correct 306 ms 13724 KB Output is correct
16 Correct 188 ms 11812 KB Output is correct
17 Correct 45 ms 10324 KB Output is correct
18 Correct 86 ms 10716 KB Output is correct
19 Correct 8 ms 9940 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Execution timed out 1063 ms 14380 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 720 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10452 KB Output is correct
2 Correct 89 ms 10992 KB Output is correct
3 Correct 160 ms 21108 KB Output is correct
4 Correct 403 ms 24780 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 952 ms 27356 KB Output is correct
8 Correct 668 ms 22284 KB Output is correct
9 Correct 162 ms 11316 KB Output is correct
10 Correct 576 ms 21824 KB Output is correct
11 Correct 390 ms 16796 KB Output is correct
12 Correct 140 ms 11276 KB Output is correct
13 Correct 184 ms 10788 KB Output is correct
14 Correct 222 ms 13848 KB Output is correct
15 Correct 306 ms 13724 KB Output is correct
16 Correct 188 ms 11812 KB Output is correct
17 Correct 45 ms 10324 KB Output is correct
18 Correct 86 ms 10716 KB Output is correct
19 Correct 8 ms 9940 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Correct 55 ms 10884 KB Output is correct
22 Correct 100 ms 11432 KB Output is correct
23 Correct 238 ms 20036 KB Output is correct
24 Correct 346 ms 24632 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 6 ms 9848 KB Output is correct
27 Correct 896 ms 24676 KB Output is correct
28 Correct 784 ms 22940 KB Output is correct
29 Correct 210 ms 13644 KB Output is correct
30 Correct 544 ms 21320 KB Output is correct
31 Correct 383 ms 16360 KB Output is correct
32 Correct 107 ms 11144 KB Output is correct
33 Correct 134 ms 10644 KB Output is correct
34 Correct 373 ms 13860 KB Output is correct
35 Correct 238 ms 11440 KB Output is correct
36 Correct 191 ms 11960 KB Output is correct
37 Correct 7 ms 9876 KB Output is correct
38 Correct 7 ms 10000 KB Output is correct
39 Execution timed out 1063 ms 14380 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10452 KB Output is correct
2 Correct 89 ms 10992 KB Output is correct
3 Correct 160 ms 21108 KB Output is correct
4 Correct 403 ms 24780 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 952 ms 27356 KB Output is correct
8 Correct 668 ms 22284 KB Output is correct
9 Correct 162 ms 11316 KB Output is correct
10 Correct 576 ms 21824 KB Output is correct
11 Correct 390 ms 16796 KB Output is correct
12 Correct 140 ms 11276 KB Output is correct
13 Correct 184 ms 10788 KB Output is correct
14 Correct 222 ms 13848 KB Output is correct
15 Correct 306 ms 13724 KB Output is correct
16 Correct 188 ms 11812 KB Output is correct
17 Correct 45 ms 10324 KB Output is correct
18 Correct 86 ms 10716 KB Output is correct
19 Correct 8 ms 9940 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Correct 55 ms 10884 KB Output is correct
22 Correct 100 ms 11432 KB Output is correct
23 Correct 238 ms 20036 KB Output is correct
24 Correct 346 ms 24632 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 6 ms 9848 KB Output is correct
27 Correct 896 ms 24676 KB Output is correct
28 Correct 784 ms 22940 KB Output is correct
29 Correct 210 ms 13644 KB Output is correct
30 Correct 544 ms 21320 KB Output is correct
31 Correct 383 ms 16360 KB Output is correct
32 Correct 107 ms 11144 KB Output is correct
33 Correct 134 ms 10644 KB Output is correct
34 Correct 373 ms 13860 KB Output is correct
35 Correct 238 ms 11440 KB Output is correct
36 Correct 191 ms 11960 KB Output is correct
37 Correct 7 ms 9876 KB Output is correct
38 Correct 7 ms 10000 KB Output is correct
39 Execution timed out 1063 ms 14380 KB Time limit exceeded
40 Halted 0 ms 0 KB -