oj.uz

Submission #73805

# Submission time Handle Problem Language Result Execution time Memory
73805 2018-08-29T04:33:13 Z 강태규(#2274) Gorgeous Pill (FXCUP3_gorgeous) C++11
0 / 100
 3 ms 508 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
int c[300001];
int d[300001];

struct node {
    int x, y, t; llong d;
    node(int x, int y, llong d, int t) : x(x), y(y), d(d), t(t) {}
    bool operator<(const node &p) const {
        if (y != p.y) return y < p.y;
        if (x != p.x) return x > p.x;
        return t > p.t;
    }
};

llong seg[300001];
void update(int i, llong x) {
    while (i <= n) {
        seg[i] = max(seg[i], x);
        i += i & -i;
    }
}
llong query(int i) {
    llong ret = 0;
    while (i) {
        ret = max(ret, seg[i]);
        i -= i & -i;
    }
    return ret;
}

llong ans[300001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", c + i);
    for (int i = 1; i <= n; ++i) scanf("%d", d + i);
    priority_queue<node> pq;
    for (int i = 1; i <= n; ++i) {
        if (c[i] == 1) {
            ans[i] += d[i];
            continue;
        }
        if (i < n && i + c[i] - 1 <= n) pq.emplace(i, i + c[i] - 1, d[i], 1);
        if (1 <= i - c[i] + 1 && 1 < i) pq.emplace(i - c[i] + 1, i, d[i], 2);
    }
    
    int pr = n;
    while (!pq.empty()) {
        node n = pq.top(); pq.pop();
        while (n.y < pr) ans[pr] += query(pr), --pr;
        if (n.t == 0) {
            update(n.x, n.d);
            continue;
        }
        int v = query(n.x) + n.d;
        if (n.t == 1) pq.emplace(n.x + 1, n.y, v, 0);
        else pq.emplace(n.x, n.y - 1, v, 0);
    }
    while (0 < pr) ans[pr] += query(pr), --pr;
    for (int i = 1; i <= n; ++i) {
        printf("%lld%c", ans[i], "\n "[i < n]);
    }
	return 0;
}

Compilation message

gorgeous.cpp: In constructor 'node::node(int, int, llong, int)':
gorgeous.cpp:26:24: warning: 'node::d' will be initialized after [-Wreorder]
     int x, y, t; llong d;
                        ^
gorgeous.cpp:26:15: warning:   'int node::t' [-Wreorder]
     int x, y, t; llong d;
               ^
gorgeous.cpp:27:5: warning:   when initialized here [-Wreorder]
     node(int x, int y, llong d, int t) : x(x), y(y), d(d), t(t) {}
     ^~~~
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
gorgeous.cpp:54:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf("%d", c + i);
                                  ~~~~~^~~~~~~~~~~~~
gorgeous.cpp:55:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf("%d", d + i);
                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Incorrect 3 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Incorrect 3 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Incorrect 3 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -