제출 #715690

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715690		raysh07	Meteors (POI11_met)	C++17	74 / 100	6057 ms	65536 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 69;
int n, m, k;
int a[N], gat[N], l[N], r[N], met[N], seg[4 * N], lazy[4 * N];
int lo[N], hi[N], mid[N];
vector <int> adj[N], sec[N];

void UpdateLazy(int l, int r, int pos){
    seg[pos] += lazy[pos];
    if (l==r) {
        lazy[pos] = 0;
        return;
    }
    
    int mid = (l+r)/2;
    lazy[pos * 2] += lazy[pos];
    lazy[pos * 2 + 1] += lazy[pos];
    lazy[pos] = 0;
    return;
}

void Update(int l, int r, int pos, int ql, int qr, int val){
    if (lazy[pos] != 0) UpdateLazy(l, r, pos);
    
    if (l>=ql && r<=qr){
        seg[pos] += val;
        if (l==r) return;
        
        lazy[pos * 2] += val;
        lazy[pos * 2 + 1] += val;
        return;
    } else if (l>qr || r<ql) return;
    
    int mid = (l+r)/2;
    Update(l, mid, pos*2, ql, qr, val);
    Update(mid + 1, r, pos*2 + 1, ql, qr, val);
    seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);
}

int Query(int l, int r, int pos, int qp){
    if (lazy[pos] != 0) UpdateLazy(l, r, pos);
    
    if (l==r) return seg[pos];
    
    int mid = (l+r)/2;
    if (qp<=mid) return Query(l, mid, pos*2, qp);
    else return Query(mid + 1, r, pos*2 + 1, qp);
}

void gogosolve(){
    for (int i=0; i<4*N; i++) seg[i] = lazy[i] = 0;
    
    for (int i=1; i<=k + 1; i++)
    adj[i].clear();
    
    for (int i=1; i<=n; i++){
        if (lo[i] == hi[i]) continue;
        mid[i] = (lo[i] + hi[i])/2;
        adj[mid[i]].push_back(i);
    }
    
    for (int i=1; i <= k + 1; i++){
        //apply update 
        if (l[i] <= r[i]){
            Update(1, m, 1, l[i], r[i], met[i]);
        } else {
            Update(1, m, 1, l[i], m, met[i]);
            Update(1, m, 1, 1, r[i], met[i]);
        }
        
        for (auto idx : adj[i]){
            int tot = 0;
            for (int places : sec[idx]){\
                int val = Query(1, m, 1, places);
                tot += val;
                // cout<<places<<" ";
                // cout<<val<<" ";
            }
            // cout<<"\n";
            
            // cout<<i<<" "<<idx<<" ";
            // cout<<tot<<" "<<gat[idx]<<"\n";
            
            if (tot >= gat[idx]) {
                hi[idx] = mid[idx];
            } else {
                lo[idx] = mid[idx] + 1;
            }
        }
    }
}

void Solve() 
{
    cin>>n>>m;
    
    for (int i=1; i<=m; i++) {
        cin>>a[i];
        sec[a[i]].push_back(i);
    }
    for (int i=1; i<=n; i++) cin>>gat[i];
    
    cin>>k;
    for (int i=1; i<=k; i++) cin>>l[i]>>r[i]>>met[i];
    l[k + 1] = 1;
    r[k + 1] = m;
    met[k + 1] = INF;
    
    for (int i=1; i<=n; i++){
        lo[i] = 1; hi[i] = k + 1; mid[i] = (lo[i] + hi[i])/2;
    }
    
    for (int i=0; i<31; i++){
        gogosolve();
    }
    
    for (int i=1; i<=n; i++){
       // assert(lo[i] == hi[i]);
        if (lo[i] == k + 1) cout<<"NIE\n";
        else cout<<lo[i]<<"\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
 //   cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

met.cpp: In function 'void UpdateLazy(long long int, long long int, long long int)':
met.cpp:22:9: warning: unused variable 'mid' [-Wunused-variable]
   22 |     int mid = (l+r)/2;
      |         ^~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13