답안 #58976 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58976	2018-07-19T23:53:31 Z	Benq	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	5.55556 / 100	907 ms	19664 KB

brunhilda

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<class T, int SZ> struct Seg {
    T seg[2*SZ], MN = 0;
    
    Seg() {
        F0R(i,2*SZ) seg[i] = MOD;
    }
    
    T comb(T a, T b) { return min(a,b); } // easily change this to min or max
    
    void upd(int p, T value) {  // set value at position p
        for (seg[p += SZ] = value; p > 1; p >>= 1)
            seg[p>>1] = comb(seg[(p|1)^1],seg[p|1]); // non-commutative operations
    }
    
    void build() {
        F0Rd(i,SZ) seg[i] = comb(seg[2*i],seg[2*i+1]);
    }
    
    T query(int l, int r) {  // sum on interval [l, r]
        T res1 = MN, res2 = MN; r++;
        for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
            if (l&1) res1 = comb(res1,seg[l++]);
            if (r&1) res2 = comb(seg[--r],res2);
        }
        return comb(res1,res2);
    }
};

Seg<int,1<<17> S;
int m,Q, mx, ans[1000001], p[MX];
priority_queue<pi,vpi,greater<pi>> use;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m >> Q;
    F0R(i,m) {
        cin >> p[i];
        use.push({p[i],i});
        S.upd(i,0);
    }
    vi todo;
    FOR(i,1,1000001) {
        while (sz(use) && use.top().f == i) {
            S.upd(use.top().s,MOD);
            todo.pb(use.top().s);
            use.pop();
        }
        if (sz(use) == 0) {
            mx = i-1;
            break;
        }
        ans[i] = S.seg[1]+1;
        for (int j: todo) {
            S.upd(j,ans[i]);
            use.push({p[j]+i,j});
        }
        todo.clear();
    }
    F0R(i,Q) {
        int x; cin >> x;
        if (x > mx) cout << "oo";
        else cout << ans[x];
        cout << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
5.55555555556 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1400 KB	Output is correct
2	Incorrect	185 ms	5384 KB	Output isn't correct
3	Correct	33 ms	5384 KB	Output is correct
4	Incorrect	25 ms	5616 KB	Output isn't correct
5	Incorrect	59 ms	5616 KB	Output isn't correct
6	Correct	4 ms	5616 KB	Output is correct
7	Correct	39 ms	5616 KB	Output is correct
8	Correct	170 ms	5616 KB	Output is correct
9	Incorrect	277 ms	5672 KB	Output isn't correct
10	Incorrect	301 ms	5672 KB	Output isn't correct
11	Incorrect	219 ms	5672 KB	Output isn't correct
12	Incorrect	21 ms	5672 KB	Output isn't correct
13	Incorrect	571 ms	5752 KB	Output isn't correct
14	Incorrect	628 ms	5964 KB	Output isn't correct
15	Incorrect	172 ms	5964 KB	Output isn't correct
16	Incorrect	190 ms	5964 KB	Output isn't correct
17	Incorrect	62 ms	5964 KB	Output isn't correct
18	Incorrect	24 ms	5964 KB	Output isn't correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	51 ms	5964 KB	Output isn't correct
2	Incorrect	133 ms	6916 KB	Output isn't correct
3	Incorrect	752 ms	6916 KB	Output isn't correct
4	Incorrect	164 ms	6916 KB	Output isn't correct
5	Incorrect	421 ms	6916 KB	Output isn't correct
6	Incorrect	204 ms	6916 KB	Output isn't correct
7	Incorrect	52 ms	6916 KB	Output isn't correct
8	Incorrect	122 ms	6916 KB	Output isn't correct
9	Incorrect	505 ms	6916 KB	Output isn't correct
10	Incorrect	830 ms	6916 KB	Output isn't correct
11	Incorrect	804 ms	6916 KB	Output isn't correct
12	Incorrect	318 ms	6916 KB	Output isn't correct
13	Incorrect	102 ms	6916 KB	Output isn't correct
14	Incorrect	135 ms	6916 KB	Output isn't correct
15	Incorrect	630 ms	6916 KB	Output isn't correct
16	Incorrect	79 ms	6944 KB	Output isn't correct
17	Incorrect	622 ms	6944 KB	Output isn't correct
18	Incorrect	614 ms	7184 KB	Output isn't correct

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	592 ms	7184 KB	Output isn't correct
2	Incorrect	828 ms	7184 KB	Output isn't correct
3	Incorrect	788 ms	7256 KB	Output isn't correct
4	Incorrect	302 ms	7256 KB	Output isn't correct
5	Incorrect	111 ms	8372 KB	Output isn't correct
6	Incorrect	506 ms	8372 KB	Output isn't correct
7	Incorrect	291 ms	9044 KB	Output isn't correct
8	Incorrect	693 ms	9044 KB	Output isn't correct
9	Incorrect	616 ms	9044 KB	Output isn't correct
10	Incorrect	340 ms	9044 KB	Output isn't correct
11	Incorrect	204 ms	9044 KB	Output isn't correct
12	Incorrect	519 ms	9044 KB	Output isn't correct
13	Incorrect	720 ms	9696 KB	Output isn't correct
14	Incorrect	343 ms	9728 KB	Output isn't correct
15	Incorrect	529 ms	9816 KB	Output isn't correct
16	Incorrect	607 ms	9816 KB	Output isn't correct
17	Incorrect	427 ms	10392 KB	Output isn't correct
18	Incorrect	838 ms	10528 KB	Output isn't correct
19	Incorrect	102 ms	10528 KB	Output isn't correct
20	Incorrect	772 ms	11008 KB	Output isn't correct
21	Incorrect	383 ms	11056 KB	Output isn't correct
22	Incorrect	717 ms	13064 KB	Output isn't correct
23	Incorrect	99 ms	13064 KB	Output isn't correct
24	Incorrect	66 ms	13064 KB	Output isn't correct
25	Incorrect	323 ms	13064 KB	Output isn't correct
26	Incorrect	344 ms	13064 KB	Output isn't correct
27	Incorrect	800 ms	14336 KB	Output isn't correct
28	Incorrect	112 ms	14336 KB	Output isn't correct
29	Incorrect	473 ms	15060 KB	Output isn't correct
30	Incorrect	405 ms	15256 KB	Output isn't correct
31	Incorrect	128 ms	15256 KB	Output isn't correct
32	Incorrect	188 ms	15544 KB	Output isn't correct
33	Incorrect	51 ms	15544 KB	Output isn't correct
34	Incorrect	339 ms	16948 KB	Output isn't correct
35	Incorrect	156 ms	16948 KB	Output isn't correct
36	Incorrect	907 ms	18460 KB	Output isn't correct
37	Incorrect	114 ms	18460 KB	Output isn't correct
38	Incorrect	545 ms	18460 KB	Output isn't correct
39	Incorrect	93 ms	18460 KB	Output isn't correct
40	Incorrect	460 ms	18460 KB	Output isn't correct
41	Incorrect	387 ms	19664 KB	Output isn't correct
42	Incorrect	684 ms	19664 KB	Output isn't correct

답안 #58976

Compilation message

Subtask #1 5.55555555556 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
5.55555555556 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0