답안 #64442 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64442	2018-08-04T13:31:07 Z	SpeedOfMagic	Hacker (BOI15_hac)	C++17	100 / 100	777 ms	66752 KB

/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
char curFlag = 'A'; void flag() {put curFlag++ << endl;}
int getInt(){int a; get a; return a;}
//code goes here
int f(int a, int b) { //f - query you need to calculate, but for two values
    return max(a, b);
}
const int nothing = 0; //nothing means that f(x, nothing)=x
struct segTreeNode {
    int val = nothing, lazy = 0;

    segTreeNode(){}

    void update(int s) { //function that updates single node from lazy
        val += s;
    }
};

v<segTreeNode> segTree;
int n, tot;

void update(int l, int r, int s, int cur = 1, int ll = 1, int rr = tot) {
    if (segTree[cur].lazy != 0) {
        segTree[cur].update(segTree[cur].lazy);
        if(cur < tot) {
            segTree[cur * 2].lazy += segTree[cur].lazy;
            segTree[cur * 2 + 1].lazy += segTree[cur].lazy;
        }
        segTree[cur].lazy = 0;
    }

    if (l > r)
        return;

    if (l == ll && r == rr) {
        segTree[cur].update(s);
        if (cur < tot) {
            segTree[cur * 2].lazy += s;
            segTree[cur * 2 + 1].lazy += s;
        }
        return;
    }

    int mid = (ll + rr) / 2;
    update(l, min(r, mid), s, cur * 2, ll, mid);
    update(max(l, mid + 1), r, s, cur * 2 + 1, mid + 1, rr);
    segTree[cur].val = f(segTree[cur * 2].val, segTree[cur * 2 + 1].val);
}

int query(int l, int r, int cur = 1, int ll = 1, int rr = tot) {
    assert(l >= ll && r <= rr);
    if (segTree[cur].lazy != 0) {
        segTree[cur].update(segTree[cur].lazy);
        if (cur < tot) {
            segTree[cur * 2].lazy += segTree[cur].lazy;
            segTree[cur * 2 + 1].lazy += segTree[cur].lazy;
        }
        segTree[cur].lazy = 0;
    }

    if (l > r)
        return nothing;

    if (l == ll && r == rr)
        return segTree[cur].val;

    int mid = (ll + rr) / 2;

    return f(query(l, min(r, mid), cur * 2, ll, mid), query(max(l, mid + 1), r, cur * 2 + 1, mid + 1, rr));
    segTree[cur].val = f(segTree[cur * 2].val, segTree[cur * 2 + 1].val);
}

void init(vector<int> vals) {
    n = vals.size();
    tot = n;
    while(tot & (tot - 1))
        tot++;

    segTree = vector<segTreeNode>(2 * tot);
    rep(i, tot, tot + n)
        segTree[i].val = vals[i - tot];

    for(int i = tot - 1; i; i--)
        segTree[i].val = f(segTree[i * 2].val, segTree[i * 2 + 1].val);
}

void run() {
    get n;
    int v[n];
    rep(i, 0, n)
        get v[i];
    init(vint(n, 0));
    vint d[n];
    int s = 0;
    rep(j, 0, n / 2 + n % 2)
        s += v[j];
    rep(i, 0, n) {
        if (i)
            s = s - v[i - 1] + v[(i + n / 2 + n % 2 - 1 + n) % n];
        d[i] = {s, i, (i + n / 2 + n % 2 - 1 + n) % n};
    }


    sort(d, d + n);
    for (int i = n - 1; i >= 0; i--) {
        //debug(d[i][0], d[i][1] + 1, d[i][2] + 1);
        if (d[i][1] > d[i][2]) {
            update(d[i][1] + 1, n, 1);
            update(1, d[i][2] + 1, 1);
        } else {
            update(d[i][1] + 1, d[i][2] + 1, 1);
        }

        if (query(1, n) == n / 2 + n % 2) {
            put d[i][0];
            return;
        }
    }
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	428 KB	Output is correct
4	Correct	3 ms	428 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	516 KB	Output is correct
7	Correct	3 ms	592 KB	Output is correct
8	Correct	3 ms	592 KB	Output is correct
9	Correct	3 ms	592 KB	Output is correct
10	Correct	3 ms	592 KB	Output is correct
11	Correct	3 ms	592 KB	Output is correct
12	Correct	3 ms	592 KB	Output is correct
13	Correct	3 ms	616 KB	Output is correct
14	Correct	2 ms	616 KB	Output is correct
15	Correct	2 ms	616 KB	Output is correct
16	Correct	3 ms	616 KB	Output is correct
17	Correct	4 ms	620 KB	Output is correct
18	Correct	4 ms	712 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	428 KB	Output is correct
4	Correct	3 ms	428 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	516 KB	Output is correct
7	Correct	3 ms	592 KB	Output is correct
8	Correct	3 ms	592 KB	Output is correct
9	Correct	3 ms	592 KB	Output is correct
10	Correct	3 ms	592 KB	Output is correct
11	Correct	3 ms	592 KB	Output is correct
12	Correct	3 ms	592 KB	Output is correct
13	Correct	3 ms	616 KB	Output is correct
14	Correct	2 ms	616 KB	Output is correct
15	Correct	2 ms	616 KB	Output is correct
16	Correct	3 ms	616 KB	Output is correct
17	Correct	4 ms	620 KB	Output is correct
18	Correct	4 ms	712 KB	Output is correct
19	Correct	3 ms	712 KB	Output is correct
20	Correct	4 ms	712 KB	Output is correct
21	Correct	3 ms	712 KB	Output is correct
22	Correct	6 ms	876 KB	Output is correct
23	Correct	9 ms	1176 KB	Output is correct
24	Correct	7 ms	1176 KB	Output is correct
25	Correct	8 ms	1184 KB	Output is correct
26	Correct	7 ms	1184 KB	Output is correct
27	Correct	3 ms	1184 KB	Output is correct
28	Correct	2 ms	1184 KB	Output is correct
29	Correct	2 ms	1184 KB	Output is correct
30	Correct	5 ms	1184 KB	Output is correct
31	Correct	7 ms	1184 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1184 KB	Output is correct
2	Correct	2 ms	1184 KB	Output is correct
3	Correct	8 ms	1184 KB	Output is correct
4	Correct	104 ms	9720 KB	Output is correct
5	Correct	323 ms	22092 KB	Output is correct
6	Correct	279 ms	26476 KB	Output is correct
7	Correct	516 ms	39096 KB	Output is correct
8	Correct	777 ms	54052 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	428 KB	Output is correct
4	Correct	3 ms	428 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	516 KB	Output is correct
7	Correct	3 ms	592 KB	Output is correct
8	Correct	3 ms	592 KB	Output is correct
9	Correct	3 ms	592 KB	Output is correct
10	Correct	3 ms	592 KB	Output is correct
11	Correct	3 ms	592 KB	Output is correct
12	Correct	3 ms	592 KB	Output is correct
13	Correct	3 ms	616 KB	Output is correct
14	Correct	2 ms	616 KB	Output is correct
15	Correct	2 ms	616 KB	Output is correct
16	Correct	3 ms	616 KB	Output is correct
17	Correct	4 ms	620 KB	Output is correct
18	Correct	4 ms	712 KB	Output is correct
19	Correct	3 ms	712 KB	Output is correct
20	Correct	4 ms	712 KB	Output is correct
21	Correct	3 ms	712 KB	Output is correct
22	Correct	6 ms	876 KB	Output is correct
23	Correct	9 ms	1176 KB	Output is correct
24	Correct	7 ms	1176 KB	Output is correct
25	Correct	8 ms	1184 KB	Output is correct
26	Correct	7 ms	1184 KB	Output is correct
27	Correct	3 ms	1184 KB	Output is correct
28	Correct	2 ms	1184 KB	Output is correct
29	Correct	2 ms	1184 KB	Output is correct
30	Correct	5 ms	1184 KB	Output is correct
31	Correct	7 ms	1184 KB	Output is correct
32	Correct	2 ms	1184 KB	Output is correct
33	Correct	2 ms	1184 KB	Output is correct
34	Correct	8 ms	1184 KB	Output is correct
35	Correct	104 ms	9720 KB	Output is correct
36	Correct	323 ms	22092 KB	Output is correct
37	Correct	279 ms	26476 KB	Output is correct
38	Correct	516 ms	39096 KB	Output is correct
39	Correct	777 ms	54052 KB	Output is correct
40	Correct	13 ms	54052 KB	Output is correct
41	Correct	32 ms	54052 KB	Output is correct
42	Correct	28 ms	54052 KB	Output is correct
43	Correct	304 ms	54052 KB	Output is correct
44	Correct	725 ms	57380 KB	Output is correct
45	Correct	100 ms	57380 KB	Output is correct
46	Correct	282 ms	57380 KB	Output is correct
47	Correct	755 ms	61072 KB	Output is correct
48	Correct	387 ms	63636 KB	Output is correct
49	Correct	627 ms	65192 KB	Output is correct
50	Correct	479 ms	66752 KB	Output is correct

답안 #64442

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 40.0 / 40.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
40.0 / 40.0