oj.uz

답안 #1015736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015736 2024-07-06T17:39:51 Z vjudge1 Meteors (POI11_met) C++17
74 / 100
 1376 ms 65536 KB 
//
//  main1.cpp
//  problem1
//
//  Created by Essa Almousa on 2030 / 01/ 01 AD.
//

#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
using ll = int;
using ll1 = int;
#define pb push_back
#define pF first
#define pS second
#define SP <<" "<<
const ll N = 3e5+10;

struct segment {
    vector<ll> tree;
    ll offset = 1;
    void it(ll n) {
        while (offset < n) offset *= 2;
        tree.resize(offset*2, 0);
    }
    void upd(ll v, ll l, ll r, ll ql, ll qr, ll x) {
        if (l >= qr || r <= ql) return;
        if (l >= ql && r <= qr) {tree[v] = min(tree[v] + x, (int)1e9); return;}
        ll mi = (l+r)/2;
        upd(v*2, l, mi, ql, qr, x);
        upd(v*2+1, mi, r, ql, qr, x);
    }
    ll query(ll i) {
        i--;
        i += offset;
        ll ans = 0;
        while (i >= 1) {
            ans = min(ans + tree[i], (int)1e9);
            i /= 2;
        }
        return ans;
    }
    void upd(ll l, ll r, ll val) {return upd(1, 0, offset, l-1, r, val);}
};

struct query_ {
    ll l, r, x;
};
ll a[N], b[N];
ll1 sol[N];
vector<ll> frq[N];
query_ q[N];

int main() {
    //ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    ll1 n, m;
    cin>>n>>m;
    for (ll i=1; i<=m; i++) {
        int temp; cin >> temp;
        a[i] = temp;
        //cin>>a[i];
        frq[a[i]].pb(i);
    }
    
    for (ll i=1; i<=n; i++) {
        int temp; cin >> temp;
        b[i] = temp;
        //cin>>b[i];
    }
    
    ll1 q1;
    cin>>q1;
    
    struct binnode { ll i, l, r; };
    
    vector<binnode> bin[N];
    for (ll i=1; i<=n; i++) {
        ll mi = q1+1/2;
        bin[mi].pb({i, 1, q1});
        sol[i] = -1;
    }

    for (ll i=1; i<=q1; i++) {
        ll1 l, r, x;
        cin>>l>>r>>x;
        q[i] = {l, r, x};
    }
    ll1 cnt = n;
    while (cnt > 0) {
        segment tree;
        tree.it(m);
        for (ll i=1; i<=q1; i++) {
            if (q[i].l > q[i].r) {
                tree.upd(q[i].l, m, q[i].x);
                tree.upd(1, q[i].r, q[i].x);
            }
            else tree.upd(q[i].l, q[i].r, q[i].x);
            
            for (ll1 j = bin[i].size()-1; j >= 0; j = bin[i].size()-1) {
                binnode& x = bin[i][j];
                ll ans = 0; // the num
                for (ll k=0; k < frq[x.i].size(); k++) ans = min(ans + tree.query(frq[x.i][k]), (int)1e9);
                if (ans >= b[x.i]) x.r = i;
                else {
                    if (x.l >= q1) {cnt--;bin[i].pop_back(); continue;};
                    x.l = i +1;
                }
                if (x.l != x.r) {bin[(x.l+x.r)/2].pb({x.i, x.l, x.r}); cnt++;}
                else sol[x.i] = x.l;
                bin[i].pop_back();
                cnt--;
                j = bin[i].size() - 1;
            }
        }
    }
    for (ll i=1; i<=n; i++) {
        if (sol[i] == -1) cout << "NIE" << endl;
        else cout << sol[i] << endl;
    }
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:103:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 for (ll k=0; k < frq[x.i].size(); k++) ans = min(ans + tree.query(frq[x.i][k]), (int)1e9);
      |                              ~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 17756 KB Output is correct
2 Correct 7 ms 17604 KB Output is correct
3 Correct 8 ms 17756 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 17756 KB Output is correct
2 Correct 9 ms 17756 KB Output is correct
3 Correct 7 ms 17720 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 21072 KB Output is correct
2 Correct 193 ms 21716 KB Output is correct
3 Correct 203 ms 24508 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 23500 KB Output is correct
2 Correct 200 ms 23756 KB Output is correct
3 Correct 259 ms 26196 KB Output is correct
4 Correct 36 ms 20752 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 22296 KB Output is correct
2 Correct 112 ms 24104 KB Output is correct
3 Correct 119 ms 20000 KB Output is correct
4 Correct 218 ms 25216 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 20968 KB Output is correct
2 Correct 189 ms 23520 KB Output is correct
3 Correct 192 ms 21500 KB Output is correct
4 Correct 225 ms 27176 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1183 ms 61496 KB Output is correct
2 Correct 737 ms 34120 KB Output is correct
3 Correct 553 ms 22384 KB Output is correct
4 Runtime error 1018 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1376 ms 50760 KB Output is correct
2 Correct 606 ms 26576 KB Output is correct
3 Correct 495 ms 19976 KB Output is correct
4 Runtime error 817 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -