oj.uz

답안 #73809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73809 2018-08-29T04:43:03 Z 강태규(#2274) 놀이터에 떨어진 이상한 약 (FXCUP3_gorgeous) C++11
100 / 100
 755 ms 53532 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) {
        pq.emplace(i, i, 0, 3);
        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);
    }
    
    while (!pq.empty()) {
        node n = pq.top(); pq.pop();
        if (n.t == 0) {
            update(n.x, n.d);
            continue;
        }
        if (n.t == 3) {
            ans[n.x] += query(n.x);
            continue;
        }
        llong 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);
    }
    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
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 3 ms 676 KB Output is correct
12 Correct 4 ms 688 KB Output is correct
13 Correct 3 ms 688 KB Output is correct
14 Correct 3 ms 792 KB Output is correct
15 Correct 5 ms 808 KB Output is correct

Subtask #3
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 3 ms 676 KB Output is correct
12 Correct 4 ms 688 KB Output is correct
13 Correct 3 ms 688 KB Output is correct
14 Correct 3 ms 792 KB Output is correct
15 Correct 5 ms 808 KB Output is correct
16 Correct 9 ms 1188 KB Output is correct
17 Correct 45 ms 2712 KB Output is correct
18 Correct 169 ms 8632 KB Output is correct
19 Correct 215 ms 11052 KB Output is correct
20 Correct 660 ms 27628 KB Output is correct
21 Correct 667 ms 32656 KB Output is correct
22 Correct 732 ms 37456 KB Output is correct
23 Correct 755 ms 42308 KB Output is correct
24 Correct 703 ms 47012 KB Output is correct
25 Correct 694 ms 53532 KB Output is correct