oj.uz

답안 #529985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529985 2022-02-24T08:57:24 Z syl123456 Dungeon 3 (JOI21_ho_t5) C++17
14 / 100
 481 ms 40956 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<ll, int> pl;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    int a[n], b[n];
    for (int &i : a)
        cin >> i;
    for (int &i : b)
        cin >> i;
    if (false && n <= 3000 && q <= 3000) {
        ll pre[n + 1];
        pre[0] = 0;
        for (int i = 0; i < n; ++i)
            pre[i + 1] = pre[i] + a[i];
        while (q--) {
            int s, t, u;
            cin >> s >> t >> u;
            --s, --t;
            ll res = 0;
            deque<pi> q;
            for (int i = s; i < t; ++i) {
                if (a[i] > u) {
                    res = -1;
                    break;
                }
                while (!q.empty() && q.back().first >= b[i])
                    q.pop_back();
                q.emplace_back(b[i], i);
                ll tmp = 0;
                while (tmp < a[i]) {
                    while (pre[i] + tmp - pre[q.front().second] >= u)
                        q.pop_front();
                    ll x = min(a[i] - tmp, u - (pre[i] + tmp - pre[q.front().second]));
                    res += x * q.front().first;
                    tmp += x;
                }
            }
            cout << res << '\n';
        }
    }
    else {
        int s[q], t[q], u[q];
        for (int i = 0; i < q; ++i)
            cin >> s[i] >> t[i] >> u[i], --s[i], --t[i];
        assert(*min_element(u, u + q) == *max_element(u, u + q));
        int U = u[0];
        ll pre[n + 1];
        pre[0] = 0;
        for (int i = 0; i < n; ++i)
            pre[i + 1] = pre[i] + a[i];
        vector<vector<int>> qry(n);
        for (int i = 0; i < q; ++i)
            qry[s[i]].push_back(i);
        vector<pl> stk;
        map<ll, ll> suf;
        ll ans[q];
        for (int i = n - 1; ~i; --i) {
            if (a[i] > U)
                stk.clear(), suf.clear();
            int tmp = inf;
            while (!stk.empty() && stk.back().second >= b[i] && stk.back().first < pre[i] + U)
                tmp = stk.back().second, suf.erase(stk.back().first), stk.pop_back();
            if (stk.empty())
                stk.emplace_back(pre[i] + U, inf), suf[pre[i] + U] = 0;
            if (stk.back().first > pre[i] + U) {
                suf[pre[i] + U] = suf[stk.back().first] + tmp * (stk.back().first - pre[i] - U);
                stk.emplace_back(pre[i] + U, tmp);
            }
            suf[pre[i]] = suf[stk.back().first] + b[i] * (stk.back().first - pre[i]);
            stk.emplace_back(pre[i], b[i]);
            for (int j : qry[i]) {
                if (pre[t[j]] > stk[0].first) {
                    ans[j] = -1;
                    continue;
                }
                auto it = suf.upper_bound(pre[t[j]]);
                --it;
                ans[j] = suf[pre[i]] - it->second;
                auto it2 = lower_bound(all(stk), pl(it->first, inf), [](pl x, pl y) {return x > y;});
                ans[j] += it2->second * (pre[t[j]] - it->first);
            }
        }
        for (ll i : ans)
            cout << i << '\n';
    }
}
/*
sort s >
all pre, pre + u
add point, range min, ans query (range sum)

range min: prefix min


*/

Compilation message

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 8732 KB Output is correct
2 Correct 51 ms 7480 KB Output is correct
3 Correct 95 ms 10316 KB Output is correct
4 Correct 101 ms 10196 KB Output is correct
5 Correct 46 ms 6564 KB Output is correct
6 Correct 427 ms 39928 KB Output is correct
7 Correct 330 ms 29616 KB Output is correct
8 Correct 481 ms 40944 KB Output is correct
9 Correct 396 ms 40956 KB Output is correct
10 Correct 456 ms 39656 KB Output is correct
11 Correct 464 ms 39180 KB Output is correct
12 Correct 450 ms 40152 KB Output is correct
13 Correct 168 ms 24028 KB Output is correct
14 Correct 153 ms 24116 KB Output is correct
15 Correct 315 ms 36236 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 78 ms 8388 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -