oj.uz

답안 #682299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682299 2023-01-16T05:57:42 Z vjudge1 푸드 코트 (JOI21_foodcourt) C++17
9 / 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), g[N];
ll t[N], l[N], r[N], c[N], k[N];

void kigash() {
    ll n, m, q;
    cin>>n>>m>>q;
    if(1) {
        while(q--) {
            ll t, l, r, c, k;
            cin>>t;
            if(t==1) {
                cin>>l>>r>>c>>k;
                for(ll i=l; i<=r; i++) {
                    for(ll j=1; j<=k; j++) g[i].pb(c);
                }
            }
            else if(t==2) {
                cin>>l>>r>>k;
                for(ll i=l; i<=r; i++) {
                    if(sz(g[i])<=k) g[i].clear();
                    else {
                        vector<ll> tmp;
                        for(ll j=k; j<sz(g[i]); j++) tmp.pb(g[i][j]);
                        g[i] = tmp;
                    }
                }
            }
            else {
                cin>>c>>k;
                // cout<<sz(v[c])<<" ";
                if(sz(g[c])>=k) cout<<g[c][k-1]<<"\n";
                else cout<<"0\n";
            }
        }
        return;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17108 KB Output is correct
2 Correct 82 ms 17368 KB Output is correct
3 Correct 114 ms 22444 KB Output is correct
4 Correct 221 ms 24248 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 545 ms 25960 KB Output is correct
8 Correct 378 ms 23112 KB Output is correct
9 Correct 139 ms 17484 KB Output is correct
10 Correct 349 ms 22768 KB Output is correct
11 Correct 276 ms 20172 KB Output is correct
12 Correct 119 ms 17480 KB Output is correct
13 Correct 155 ms 17264 KB Output is correct
14 Correct 234 ms 18708 KB Output is correct
15 Correct 223 ms 18800 KB Output is correct
16 Correct 167 ms 17768 KB Output is correct
17 Correct 44 ms 17000 KB Output is correct
18 Correct 82 ms 17304 KB Output is correct
19 Correct 10 ms 16852 KB Output is correct
20 Correct 10 ms 16852 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17108 KB Output is correct
2 Correct 82 ms 17368 KB Output is correct
3 Correct 114 ms 22444 KB Output is correct
4 Correct 221 ms 24248 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 545 ms 25960 KB Output is correct
8 Correct 378 ms 23112 KB Output is correct
9 Correct 139 ms 17484 KB Output is correct
10 Correct 349 ms 22768 KB Output is correct
11 Correct 276 ms 20172 KB Output is correct
12 Correct 119 ms 17480 KB Output is correct
13 Correct 155 ms 17264 KB Output is correct
14 Correct 234 ms 18708 KB Output is correct
15 Correct 223 ms 18800 KB Output is correct
16 Correct 167 ms 17768 KB Output is correct
17 Correct 44 ms 17000 KB Output is correct
18 Correct 82 ms 17304 KB Output is correct
19 Correct 10 ms 16852 KB Output is correct
20 Correct 10 ms 16852 KB Output is correct
21 Runtime error 418 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 526 ms 18508 KB Output is correct
2 Correct 409 ms 18676 KB Output is correct
3 Correct 569 ms 18704 KB Output is correct
4 Correct 518 ms 18692 KB Output is correct
5 Correct 384 ms 18764 KB Output is correct
6 Correct 396 ms 18764 KB Output is correct
7 Correct 23 ms 16724 KB Output is correct
8 Correct 23 ms 16852 KB Output is correct
9 Correct 826 ms 18608 KB Output is correct
10 Correct 844 ms 19272 KB Output is correct
11 Correct 862 ms 19312 KB Output is correct
12 Correct 853 ms 19344 KB Output is correct
13 Correct 167 ms 19012 KB Output is correct
14 Correct 258 ms 19536 KB Output is correct
15 Correct 51 ms 18892 KB Output is correct
16 Correct 61 ms 19492 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 409 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17108 KB Output is correct
2 Correct 82 ms 17368 KB Output is correct
3 Correct 114 ms 22444 KB Output is correct
4 Correct 221 ms 24248 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 545 ms 25960 KB Output is correct
8 Correct 378 ms 23112 KB Output is correct
9 Correct 139 ms 17484 KB Output is correct
10 Correct 349 ms 22768 KB Output is correct
11 Correct 276 ms 20172 KB Output is correct
12 Correct 119 ms 17480 KB Output is correct
13 Correct 155 ms 17264 KB Output is correct
14 Correct 234 ms 18708 KB Output is correct
15 Correct 223 ms 18800 KB Output is correct
16 Correct 167 ms 17768 KB Output is correct
17 Correct 44 ms 17000 KB Output is correct
18 Correct 82 ms 17304 KB Output is correct
19 Correct 10 ms 16852 KB Output is correct
20 Correct 10 ms 16852 KB Output is correct
21 Correct 526 ms 18508 KB Output is correct
22 Correct 409 ms 18676 KB Output is correct
23 Correct 569 ms 18704 KB Output is correct
24 Correct 518 ms 18692 KB Output is correct
25 Correct 384 ms 18764 KB Output is correct
26 Correct 396 ms 18764 KB Output is correct
27 Correct 23 ms 16724 KB Output is correct
28 Correct 23 ms 16852 KB Output is correct
29 Correct 826 ms 18608 KB Output is correct
30 Correct 844 ms 19272 KB Output is correct
31 Correct 862 ms 19312 KB Output is correct
32 Correct 853 ms 19344 KB Output is correct
33 Correct 167 ms 19012 KB Output is correct
34 Correct 258 ms 19536 KB Output is correct
35 Correct 51 ms 18892 KB Output is correct
36 Correct 61 ms 19492 KB Output is correct
37 Execution timed out 1082 ms 31944 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 403 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17108 KB Output is correct
2 Correct 82 ms 17368 KB Output is correct
3 Correct 114 ms 22444 KB Output is correct
4 Correct 221 ms 24248 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 545 ms 25960 KB Output is correct
8 Correct 378 ms 23112 KB Output is correct
9 Correct 139 ms 17484 KB Output is correct
10 Correct 349 ms 22768 KB Output is correct
11 Correct 276 ms 20172 KB Output is correct
12 Correct 119 ms 17480 KB Output is correct
13 Correct 155 ms 17264 KB Output is correct
14 Correct 234 ms 18708 KB Output is correct
15 Correct 223 ms 18800 KB Output is correct
16 Correct 167 ms 17768 KB Output is correct
17 Correct 44 ms 17000 KB Output is correct
18 Correct 82 ms 17304 KB Output is correct
19 Correct 10 ms 16852 KB Output is correct
20 Correct 10 ms 16852 KB Output is correct
21 Runtime error 418 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17108 KB Output is correct
2 Correct 82 ms 17368 KB Output is correct
3 Correct 114 ms 22444 KB Output is correct
4 Correct 221 ms 24248 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 545 ms 25960 KB Output is correct
8 Correct 378 ms 23112 KB Output is correct
9 Correct 139 ms 17484 KB Output is correct
10 Correct 349 ms 22768 KB Output is correct
11 Correct 276 ms 20172 KB Output is correct
12 Correct 119 ms 17480 KB Output is correct
13 Correct 155 ms 17264 KB Output is correct
14 Correct 234 ms 18708 KB Output is correct
15 Correct 223 ms 18800 KB Output is correct
16 Correct 167 ms 17768 KB Output is correct
17 Correct 44 ms 17000 KB Output is correct
18 Correct 82 ms 17304 KB Output is correct
19 Correct 10 ms 16852 KB Output is correct
20 Correct 10 ms 16852 KB Output is correct
21 Runtime error 418 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -