Submission #715690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
715690	2023-03-27T14:07:00 Z	raysh07	Meteors (POI11_met)	C++17	74 / 100	6000 ms	65536 KB

#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;
}

Compilation message

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	33348 KB	Output is correct
2	Correct	84 ms	33364 KB	Output is correct
3	Correct	84 ms	33360 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	33356 KB	Output is correct
2	Correct	95 ms	33360 KB	Output is correct
3	Correct	86 ms	33460 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	908 ms	37256 KB	Output is correct
2	Correct	1108 ms	40824 KB	Output is correct
3	Correct	1027 ms	39632 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1000 ms	38872 KB	Output is correct
2	Correct	970 ms	38824 KB	Output is correct
3	Correct	1134 ms	41360 KB	Output is correct
4	Correct	197 ms	37372 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	397 ms	37588 KB	Output is correct
2	Correct	715 ms	41316 KB	Output is correct
3	Correct	526 ms	35136 KB	Output is correct
4	Correct	1239 ms	40336 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1156 ms	36496 KB	Output is correct
2	Correct	867 ms	38900 KB	Output is correct
3	Correct	903 ms	36960 KB	Output is correct
4	Correct	1036 ms	42596 KB	Output is correct

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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