oj.uz

답안 #680929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680929 2023-01-12T03:49:57 Z socpite Meteors (POI11_met) C++17
87 / 100
 1621 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;


#define f first
#define s second

typedef long long ll;

const int maxn = 5e5+5;
const ll inf = 1e18;

int n, m, q;
ll FW[maxn], D[maxn];

int L[maxn], R[maxn];

void add(int idx, int val){
    for(idx; idx <= n; idx+=idx&(-idx))FW[idx]+=val;
}

void radd(int l, int r, int val){
    add(l, val);
    add(r+1, -val);
}

ll gt(int idx){
    ll re = 0;
    for(idx; idx > 0; idx-=idx&(-idx))re+=FW[idx];
    return re;
}

pair<pair<int, int>, int> qq[maxn];

vector<int> vec[maxn], pos[maxn];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        pos[x].push_back(i);
    }
    for(int i = 1; i <= m; i++)cin >> D[i];
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> qq[i].f.f >> qq[i].f.s >> qq[i].s;
    }
    for(int i = 1; i <= m; i++){
        L[i] = 1;
        R[i] = q+1;
    }
    while(true){
        bool chk = 0;
        for(int i = 1; i <= m; i++){
            if(L[i] < R[i]){
                chk = 1;
                int mid = (L[i] + R[i])>>1;
                vec[mid].push_back(i);
            }
        }
        for(int i = 1; i <= q; i++){
            if(qq[i].f.f <= qq[i].f.s)radd(qq[i].f.f, qq[i].f.s, qq[i].s);
            else{
                radd(qq[i].f.f, n, qq[i].s);
                radd(1, qq[i].f.s, qq[i].s);
            }
            for(auto v: vec[i]){
                ll sum = 0;
                for(auto x: pos[v]){
                    sum+=gt(x);
                    sum = min(sum, inf);
                }
                //cout << sum << "\n";
                if(sum >= D[v])R[v] = i;
                else L[v] = i+1;
            }
        }
        for(int i = 1; i <= n; i++)FW[i]=0;
        for(int i = 1; i <= q; i++)vec[i].clear();
        if(!chk)break;
    }
    for(int i = 1; i <= m; i++){
        if(L[i] == q+1)cout << "NIE";
        else cout << L[i];
        cout << "\n";
    }
    //ifstream cin("input.txt");
    //ofstream cout("output2.txt");

}

Compilation message

met.cpp: In function 'void add(int, int)':
met.cpp:19:9: warning: statement has no effect [-Wunused-value]
   19 |     for(idx; idx <= n; idx+=idx&(-idx))FW[idx]+=val;
      |         ^~~
met.cpp: In function 'll gt(int)':
met.cpp:29:9: warning: statement has no effect [-Wunused-value]
   29 |     for(idx; idx > 0; idx-=idx&(-idx))re+=FW[idx];
      |         ^~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23896 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 15 ms 23904 KB Output is correct
3 Correct 15 ms 23892 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 25588 KB Output is correct
2 Correct 110 ms 27604 KB Output is correct
3 Correct 95 ms 27208 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 26632 KB Output is correct
2 Correct 106 ms 26620 KB Output is correct
3 Correct 107 ms 27800 KB Output is correct
4 Correct 36 ms 26016 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 26008 KB Output is correct
2 Correct 88 ms 28256 KB Output is correct
3 Correct 50 ms 24512 KB Output is correct
4 Correct 99 ms 27616 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 25144 KB Output is correct
2 Correct 108 ms 26660 KB Output is correct
3 Correct 78 ms 25420 KB Output is correct
4 Correct 117 ms 28960 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 911 ms 43712 KB Output is correct
2 Correct 649 ms 31024 KB Output is correct
3 Correct 220 ms 29408 KB Output is correct
4 Correct 1621 ms 65536 KB Output is correct

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 923 ms 42224 KB Output is correct
2 Correct 655 ms 31012 KB Output is correct
3 Correct 193 ms 29652 KB Output is correct
4 Runtime error 1609 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -