oj.uz

Submission #61403

# Submission time Handle Problem Language Result Execution time Memory
61403 2018-07-25T18:57:22 Z Benq Candies (JOI18_candies) C++11
8 / 100
 121 ms 18076 KB 
#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 = 100005;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ], L[SZ], R[SZ];
    ll val[SZ];
    
    DSU() {
        F0R(i,SZ) par[i] = L[i] = R[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    void unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	L[x] = min(L[x],L[y]);
    	R[x] = max(R[x],R[y]);
    }
};

DSU<MX> D;
int N, A[2001];
ll cans;
set<pl> cur;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) {
        cin >> A[i];
        cur.insert({A[i],i});
        D.val[i] = A[i];
    }
    FOR(i,1,(N+1)/2+1) {
        pl tmp = *cur.rbegin(); cur.erase(tmp);
        tmp.s = D.get(tmp.s);
        cans += tmp.f;
        cout << cans << "\n";
        
        int l = D.get(D.L[tmp.s]-1), r = D.get(D.R[tmp.s]+1);
        ll nval = D.val[l]+D.val[r]-D.val[tmp.s];
        if (D.L[l] != 0) cur.erase({D.val[l],l});
        if (D.R[r] != N+1) cur.erase({D.val[r],r});
        
        D.unite(l,tmp.s), D.unite(tmp.s,r);
        tmp.s = D.get(tmp.s);
        if (D.L[tmp.s] != 0 && D.R[tmp.s] != N+1)
            cur.insert({D.val[tmp.s] = nval,tmp.s});
    }
}

/* 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2044 KB Output is correct
2 Correct 6 ms 2284 KB Output is correct
3 Correct 6 ms 2284 KB Output is correct
4 Correct 8 ms 2320 KB Output is correct
5 Correct 7 ms 2320 KB Output is correct
6 Correct 7 ms 2408 KB Output is correct
7 Correct 6 ms 2408 KB Output is correct
8 Correct 8 ms 2408 KB Output is correct
9 Correct 6 ms 2408 KB Output is correct
10 Correct 5 ms 2408 KB Output is correct
11 Correct 6 ms 2408 KB Output is correct
12 Correct 6 ms 2468 KB Output is correct
13 Correct 6 ms 2468 KB Output is correct
14 Correct 5 ms 2468 KB Output is correct
15 Correct 7 ms 2468 KB Output is correct
16 Correct 6 ms 2468 KB Output is correct
17 Correct 7 ms 2468 KB Output is correct
18 Correct 6 ms 2468 KB Output is correct
19 Correct 6 ms 2468 KB Output is correct
20 Correct 6 ms 2468 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2044 KB Output is correct
2 Correct 6 ms 2284 KB Output is correct
3 Correct 6 ms 2284 KB Output is correct
4 Correct 8 ms 2320 KB Output is correct
5 Correct 7 ms 2320 KB Output is correct
6 Correct 7 ms 2408 KB Output is correct
7 Correct 6 ms 2408 KB Output is correct
8 Correct 8 ms 2408 KB Output is correct
9 Correct 6 ms 2408 KB Output is correct
10 Correct 5 ms 2408 KB Output is correct
11 Correct 6 ms 2408 KB Output is correct
12 Correct 6 ms 2468 KB Output is correct
13 Correct 6 ms 2468 KB Output is correct
14 Correct 5 ms 2468 KB Output is correct
15 Correct 7 ms 2468 KB Output is correct
16 Correct 6 ms 2468 KB Output is correct
17 Correct 7 ms 2468 KB Output is correct
18 Correct 6 ms 2468 KB Output is correct
19 Correct 6 ms 2468 KB Output is correct
20 Correct 6 ms 2468 KB Output is correct
21 Runtime error 121 ms 18076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -