Submission #58977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58977	2018-07-19T23:54:35 Z	Benq	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	5.55556 / 100	1000 ms	42444 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[10000001], 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,10000001) {
        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

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1400 KB	Output is correct
2	Execution timed out	1085 ms	25528 KB	Time limit exceeded
3	Correct	37 ms	25528 KB	Output is correct
4	Incorrect	198 ms	40628 KB	Output isn't correct
5	Incorrect	558 ms	40628 KB	Output isn't correct
6	Correct	5 ms	40628 KB	Output is correct
7	Correct	35 ms	40628 KB	Output is correct
8	Correct	153 ms	40628 KB	Output is correct
9	Execution timed out	1090 ms	40628 KB	Time limit exceeded
10	Execution timed out	1062 ms	40628 KB	Time limit exceeded
11	Execution timed out	1087 ms	40628 KB	Time limit exceeded
12	Incorrect	167 ms	40760 KB	Output isn't correct
13	Execution timed out	1080 ms	40760 KB	Time limit exceeded
14	Execution timed out	1069 ms	40760 KB	Time limit exceeded
15	Execution timed out	1088 ms	40760 KB	Time limit exceeded
16	Execution timed out	1081 ms	40760 KB	Time limit exceeded
17	Incorrect	581 ms	40764 KB	Output isn't correct
18	Incorrect	232 ms	40900 KB	Output isn't correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	558 ms	41044 KB	Output isn't correct
2	Incorrect	764 ms	42104 KB	Output isn't correct
3	Execution timed out	1086 ms	42104 KB	Time limit exceeded
4	Execution timed out	1085 ms	42104 KB	Time limit exceeded
5	Execution timed out	1070 ms	42104 KB	Time limit exceeded
6	Execution timed out	1089 ms	42104 KB	Time limit exceeded
7	Incorrect	563 ms	42104 KB	Output isn't correct
8	Execution timed out	1025 ms	42104 KB	Time limit exceeded
9	Execution timed out	1091 ms	42104 KB	Time limit exceeded
10	Execution timed out	1091 ms	42104 KB	Time limit exceeded
11	Execution timed out	1071 ms	42104 KB	Time limit exceeded
12	Execution timed out	1075 ms	42104 KB	Time limit exceeded
13	Incorrect	695 ms	42104 KB	Output isn't correct
14	Execution timed out	1091 ms	42104 KB	Time limit exceeded
15	Execution timed out	1090 ms	42104 KB	Time limit exceeded
16	Incorrect	763 ms	42152 KB	Output isn't correct
17	Execution timed out	1086 ms	42152 KB	Time limit exceeded
18	Execution timed out	1084 ms	42152 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1085 ms	42152 KB	Time limit exceeded
2	Execution timed out	1090 ms	42152 KB	Time limit exceeded
3	Execution timed out	1083 ms	42152 KB	Time limit exceeded
4	Execution timed out	1089 ms	42152 KB	Time limit exceeded
5	Incorrect	826 ms	42444 KB	Output isn't correct
6	Execution timed out	1084 ms	42444 KB	Time limit exceeded
7	Execution timed out	1091 ms	42444 KB	Time limit exceeded
8	Execution timed out	1075 ms	42444 KB	Time limit exceeded
9	Execution timed out	1085 ms	42444 KB	Time limit exceeded
10	Execution timed out	1082 ms	42444 KB	Time limit exceeded
11	Execution timed out	1088 ms	42444 KB	Time limit exceeded
12	Execution timed out	1085 ms	42444 KB	Time limit exceeded
13	Execution timed out	1091 ms	42444 KB	Time limit exceeded
14	Execution timed out	1085 ms	42444 KB	Time limit exceeded
15	Execution timed out	1086 ms	42444 KB	Time limit exceeded
16	Execution timed out	1082 ms	42444 KB	Time limit exceeded
17	Execution timed out	1080 ms	42444 KB	Time limit exceeded
18	Execution timed out	1080 ms	42444 KB	Time limit exceeded
19	Execution timed out	1078 ms	42444 KB	Time limit exceeded
20	Execution timed out	1087 ms	42444 KB	Time limit exceeded
21	Execution timed out	1081 ms	42444 KB	Time limit exceeded
22	Execution timed out	1083 ms	42444 KB	Time limit exceeded
23	Incorrect	827 ms	42444 KB	Output isn't correct
24	Incorrect	514 ms	42444 KB	Output isn't correct
25	Execution timed out	1091 ms	42444 KB	Time limit exceeded
26	Execution timed out	1082 ms	42444 KB	Time limit exceeded
27	Execution timed out	1088 ms	42444 KB	Time limit exceeded
28	Execution timed out	1053 ms	42444 KB	Time limit exceeded
29	Execution timed out	1086 ms	42444 KB	Time limit exceeded
30	Execution timed out	1083 ms	42444 KB	Time limit exceeded
31	Execution timed out	1090 ms	42444 KB	Time limit exceeded
32	Execution timed out	1085 ms	42444 KB	Time limit exceeded
33	Incorrect	306 ms	42444 KB	Output isn't correct
34	Execution timed out	1085 ms	42444 KB	Time limit exceeded
35	Execution timed out	1091 ms	42444 KB	Time limit exceeded
36	Execution timed out	1097 ms	42444 KB	Time limit exceeded
37	Incorrect	782 ms	42444 KB	Output isn't correct
38	Execution timed out	1093 ms	42444 KB	Time limit exceeded
39	Incorrect	653 ms	42444 KB	Output isn't correct
40	Execution timed out	1085 ms	42444 KB	Time limit exceeded
41	Execution timed out	1092 ms	42444 KB	Time limit exceeded
42	Execution timed out	1086 ms	42444 KB	Time limit exceeded