oj.uz

답안 #979725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979725 2024-05-11T10:25:03 Z hugo_pm Fish 3 (JOI24_fish3) C++17
28 / 100
 210 ms 50620 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
    bool first = true;
    string res = "[";
    for (const auto &x : v) {
        if (!first)
            res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "]";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
    cout << ' ' << to_string(H);
    dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Req { int lft, iReq; };
struct Itv {
    int l, r, val;
    int sumVal(int lim_l = -1e18) {
        return (r - max(lim_l, l) + 1) * val;
    }
};
bool operator<(Itv a, Itv b) { return a.l < b.l; };
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nbFish, delta;
    cin >> nbFish >> delta;
    vector<int> ideal(nbFish);
    vector<int> sumIdeal {0};
    rep(i, 0, nbFish) {
        cin >> ideal[i];
        sumIdeal.push_back(sumIdeal.back() + ideal[i]);
    }
    int nbReq; cin >> nbReq;
    vector<vector<Req>> reqs(nbFish);
    rep(iReq, 0, nbReq) {
        int lft, rgt;
        cin >> lft >> rgt;
        --lft, --rgt;
        reqs[rgt].push_back({lft, iReq});
    }
    vector<int> answers(nbReq);
    vector<Itv> stk;
    vector<int> sumStk {0} ;
    rep(rgt, 0, nbFish) {
        int valRgt = ideal[rgt];
        int pushLft = rgt;
        while (!stk.empty() && stk.back().val > valRgt) {
            pushLft = stk.back().l;
            stk.pop_back();
            sumStk.pop_back();
        }
        stk.push_back({pushLft, rgt, valRgt});
        sumStk.push_back(sumStk.back() + stk.back().sumVal());
        for (auto [lft, iReq] : reqs[rgt]) {
            int idItvContainingLft = lower_bound(all(stk), Itv {lft+1, -1, -1}) - stk.begin() - 1;
            int sumBelowIncluded = sumStk.back() - sumStk[idItvContainingLft+1];
            int belowBorder = stk[idItvContainingLft].sumVal(lft);
            
            int sumAbove = sumIdeal[rgt+1] - sumIdeal[lft];
            answers[iReq] = sumAbove - (sumBelowIncluded + belowBorder);
        }
    }
    for (int x : answers) {
        cout << x << '\n';
    }
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 39104 KB Output is correct
2 Correct 197 ms 39460 KB Output is correct
3 Incorrect 71 ms 14492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 15700 KB Output is correct
2 Correct 140 ms 36832 KB Output is correct
3 Correct 145 ms 35600 KB Output is correct
4 Correct 185 ms 35216 KB Output is correct
5 Correct 145 ms 36292 KB Output is correct
6 Correct 162 ms 31680 KB Output is correct
7 Correct 156 ms 30400 KB Output is correct
8 Correct 174 ms 34024 KB Output is correct
9 Correct 187 ms 34576 KB Output is correct
10 Correct 210 ms 50432 KB Output is correct
11 Correct 199 ms 50620 KB Output is correct
12 Correct 196 ms 41880 KB Output is correct
13 Correct 185 ms 41924 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 27336 KB Output is correct
2 Correct 159 ms 31720 KB Output is correct
3 Correct 109 ms 19408 KB Output is correct
4 Correct 181 ms 33820 KB Output is correct
5 Correct 145 ms 34560 KB Output is correct
6 Correct 177 ms 36296 KB Output is correct
7 Correct 154 ms 31592 KB Output is correct
8 Correct 160 ms 35040 KB Output is correct
9 Incorrect 159 ms 30840 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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