oj.uz

답안 #1078067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078067 2024-08-27T12:12:19 Z 0npata Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 21224 KB 
#include<bits/stdc++.h>
using namespace std;


#define vec vector
#define int long long

const int INF = 1e17;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;


    vec<int> A(N);
    set<pair<int, int>> A_s;

    for(int i = 0; i<N; i++) {
        cin >> A[i];
        A_s.insert({-A[i], i});
    }

    int Q;
    cin >> Q;
    while(Q--) {
        //cerr << "f" << '\n';
        int T;
        cin  >> T;
        int X, Y;
        cin >> X >> Y;
        X--;
        if(T==1) {
            A_s.erase({-A[X], X});
            A[X] = Y;
            A_s.insert({-Y, X});
            continue;
        }

        vec<int> l(N);
        vec<int> r(N);

        vec<pair<int, int>> hi{{INF, -1}};

        for(int i = 0; i<N; i++) {
            while(hi.back().first <= A[i]) {
                hi.pop_back();
                //cerr << "here1" << '\n';
            }
            l[i] = hi.back().second;
            cerr << l[i] << ' ';
            hi.push_back({A[i], i});
        }
        //cerr << '\n';

        vec<pair<int, int>> hi_r{{INF, N}};

        for(int i = N-1; i>=0; i--) {
            while(hi_r.back().first <= A[i]) {
                //cerr << "here2" << '\n';
                hi_r.pop_back();
            }
            r[i] = hi_r.back().second;
            hi_r.push_back({A[i], i});
        }
        for(int i = 0; i<N; i++) {
            //cerr << r[i] << ' ';
        }

        vec<bool> valid(N);
        vec<int> prefixsums(N+2);
        for(int i = 1; i<=N; i++) {
            prefixsums[i] = prefixsums[i-1] + A[i-1];
        }
        prefixsums[N+1] = prefixsums[N];

        valid[(*A_s.begin()).second] = true;
        int ans = 0;
        for(auto [_, i] : A_s) {
            int cl = l[i];
            int cr = r[i];

            int sum = prefixsums[cr]-prefixsums[cl+1];

            if(cl != -1) {
                if(sum >= A[cl]) valid[i] = valid[i] | valid[cl];
            }
            if(cr != N) {
                if(sum >= A[cr]) valid[i] = valid[i] | valid[cr];
            }
            if(cl == -1 && cr == N) valid[i] = true;
            //cerr << i << ": " << valid[i] << '\n';
            ans += valid[i];
        }

        cout << ans << '\n';
    }

}

Subtask #1
0 / 5.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 278 ms 10816 KB Output is correct
3 Correct 238 ms 10748 KB Output is correct
4 Correct 272 ms 11012 KB Output is correct
5 Correct 267 ms 10576 KB Output is correct
6 Correct 266 ms 11240 KB Output is correct
7 Correct 241 ms 10580 KB Output is correct
8 Correct 283 ms 11344 KB Output is correct
9 Correct 249 ms 10608 KB Output is correct
10 Correct 266 ms 10836 KB Output is correct
11 Correct 279 ms 10580 KB Output is correct
12 Correct 243 ms 10456 KB Output is correct
13 Correct 258 ms 10512 KB Output is correct
14 Correct 234 ms 10924 KB Output is correct
15 Correct 246 ms 10968 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 278 ms 10816 KB Output is correct
3 Correct 238 ms 10748 KB Output is correct
4 Correct 272 ms 11012 KB Output is correct
5 Correct 267 ms 10576 KB Output is correct
6 Correct 266 ms 11240 KB Output is correct
7 Correct 241 ms 10580 KB Output is correct
8 Correct 283 ms 11344 KB Output is correct
9 Correct 249 ms 10608 KB Output is correct
10 Correct 266 ms 10836 KB Output is correct
11 Correct 279 ms 10580 KB Output is correct
12 Correct 243 ms 10456 KB Output is correct
13 Correct 258 ms 10512 KB Output is correct
14 Correct 234 ms 10924 KB Output is correct
15 Correct 246 ms 10968 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 278 ms 10816 KB Output is correct
3 Correct 238 ms 10748 KB Output is correct
4 Correct 272 ms 11012 KB Output is correct
5 Correct 267 ms 10576 KB Output is correct
6 Correct 266 ms 11240 KB Output is correct
7 Correct 241 ms 10580 KB Output is correct
8 Correct 283 ms 11344 KB Output is correct
9 Correct 249 ms 10608 KB Output is correct
10 Correct 266 ms 10836 KB Output is correct
11 Correct 279 ms 10580 KB Output is correct
12 Correct 243 ms 10456 KB Output is correct
13 Correct 258 ms 10512 KB Output is correct
14 Correct 234 ms 10924 KB Output is correct
15 Correct 246 ms 10968 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Execution timed out 4072 ms 21224 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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