oj.uz

답안 #776304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776304 2023-07-07T15:49:58 Z bachhoangxuan 푸드 코트 (JOI21_foodcourt) C++17
21 / 100
 338 ms 44552 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=250005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;
int n,m,q,c[maxn],ans[maxn],lst;
vector<tuple<int,int,int>> add[maxn];
namespace Segtree{
    int tree[4*maxn],lazy[4*maxn],sum[4*maxn];
    void getnew(int id,int val){
        tree[id]+=val;
        lazy[id]+=val;
    }
    void pushdown(int id){
        if(lazy[id]==0) return;
        getnew(id<<1,lazy[id]);
        getnew(id<<1|1,lazy[id]);
        lazy[id]=0;
    }
    void update(int l,int r,int id,int p,int k){
        if(l==r){getnew(id,k);return;}
        pushdown(id);
        int mid=(l+r)>>1;
        if(p<=mid){update(l,mid,id<<1,p,k);getnew(id<<1|1,k);}
        else update(mid+1,r,id<<1|1,p,k);
        tree[id]=min(tree[id<<1],tree[id<<1|1]);
    }
    void updatesum(int l,int r,int id,int p,int k){
        if(l==r){sum[id]+=k;return;}
        int mid=(l+r)>>1;
        if(p<=mid) updatesum(l,mid,id<<1,p,k);
        else updatesum(mid+1,r,id<<1|1,p,k);
        sum[id]=sum[id<<1]+sum[id<<1|1];
    }
    int queryMin(int l,int r,int id,int p){
        if(l==r) return lst=tree[id];
        pushdown(id);
        int mid=(l+r)>>1;
        if(p<=mid) return queryMin(l,mid,id<<1,p);
        else return min(tree[id<<1],queryMin(mid+1,r,id<<1|1,p));
    }
    pii query(int l,int r,int id,int p,int cnt){
        if(l==r) return {sum[id],l};
        pushdown(id);
        int mid=(l+r)>>1;
        if(p<r){
            if(sum[id<<1|1]>=cnt) return query(mid+1,r,id<<1|1,p,cnt);
            else{
                pii f=query(l,mid,id<<1,p,cnt-sum[id<<1|1]);
                return {f.fi+sum[id<<1|1],f.se};
            }
        }
        else if(p<=mid) return query(l,mid,id<<1,p,cnt);
        else{
            pii f=query(mid+1,r,id<<1|1,p,cnt);
            if(f.fi>=cnt) return f;
            else if(f.fi+sum[id<<1]<cnt) return {f.fi+sum[id<<1],-1};
            else{
                pii g=query(l,mid,id<<1,p,cnt-f.fi);
                return {f.fi+g.fi,g.se};
            }
        }
    }
}
void solve(){
    cin >> n >> m >> q;
    for(int i=1;i<=q;i++){
        int t,l,r,k;cin >> t;ans[i]=-1;
        if(t==1) cin >> l >> r >> c[i] >> k;
        else if(t==2) cin >> l >> r >> k,k=-k;
        else cin >> l >> k;
        if(t==3) add[l].push_back({t,i,k});
        else{
            add[l].push_back({t,i,k});
            add[r+1].push_back({t,i,-k});
        }
    }
    for(int i=1;i<=n;i++){
        for(auto &[t,id,k]:add[i]){
            if(t<=2) Segtree::update(1,q,1,id,k);
            if(t==1) Segtree::updatesum(1,q,1,id,k);
            if(t==3){
                int Min=min(0LL,Segtree::queryMin(1,q,1,id));lst-=Min;
                //cout << id << ' ' << lst << ' ' << k << '\n';
                if(k>lst) ans[id]=0;
                else ans[id]=c[Segtree::query(1,q,1,id,lst-k+1).se];
            }
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[i]!=-1) cout << ans[i] << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 15140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 40500 KB Output is correct
2 Correct 196 ms 35892 KB Output is correct
3 Correct 279 ms 42648 KB Output is correct
4 Correct 207 ms 36064 KB Output is correct
5 Correct 210 ms 36856 KB Output is correct
6 Correct 326 ms 43444 KB Output is correct
7 Correct 115 ms 36612 KB Output is correct
8 Correct 121 ms 36620 KB Output is correct
9 Correct 318 ms 41176 KB Output is correct
10 Correct 310 ms 41188 KB Output is correct
11 Correct 297 ms 40336 KB Output is correct
12 Correct 325 ms 43348 KB Output is correct
13 Correct 288 ms 40508 KB Output is correct
14 Correct 305 ms 43380 KB Output is correct
15 Correct 275 ms 43148 KB Output is correct
16 Correct 289 ms 43216 KB Output is correct
17 Correct 283 ms 43212 KB Output is correct
18 Correct 287 ms 41700 KB Output is correct
19 Correct 338 ms 43244 KB Output is correct
20 Correct 277 ms 42028 KB Output is correct
21 Correct 338 ms 43352 KB Output is correct
22 Correct 309 ms 43104 KB Output is correct
23 Correct 299 ms 43232 KB Output is correct
24 Correct 283 ms 43212 KB Output is correct
25 Correct 210 ms 43956 KB Output is correct
26 Correct 225 ms 44552 KB Output is correct
27 Correct 253 ms 44392 KB Output is correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 14652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6352 KB Output isn't correct
2 Halted 0 ms 0 KB -