답안 #17428 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17428	2015-12-06T07:37:09 Z	austin990301	말 (IOI15_horses)	C++14	54 / 100	455 ms	102768 KB

horses

#pragma GCC optimize ("O3")
#pragma comment(linker , "/STACK:102400000,102400000")

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxN = 500000 + 10;
const LL mod = 1000000007LL;

struct Segt {
        static Segt *pmem , mem[maxN<<2];
        Segt *lc , *rc;
        int l , r;
        LL x;
        double log_x , log_y;

        Segt() {}
        Segt(int l0 , int r0) : l(l0) , r(r0) , x(1LL) , log_x(0.0) , log_y(0.0) {}
} Segt::mem[maxN<<2] , *Segt::pmem = Segt::mem;

Segt *tr;
LL Y[maxN];
int best_ans_pos;
double best_log_ans;

Segt* build(int l , int r) {
        Segt *tr = new (Segt::pmem++) Segt(l , r);

        if(l != r) {
                int m = (l+r)/2;

                tr->lc = build(l , m);
                tr->rc = build(m+1 , r);
        }

        return tr;
}

void modify_x(Segt *tr , int p , LL x) {
        int l = tr->l , r = tr->r;
        int m = (l+r)/2;

        if(l == r) {
                tr->x = x;
                tr->log_x = log(static_cast<double>(x));

                return;
        }

        if(p <= m) modify_x(tr->lc , p , x);
        else modify_x(tr->rc , p , x);

        tr->x = (tr->lc->x*tr->rc->x)%mod;
        tr->log_x = tr->lc->log_x+tr->rc->log_x;
}

void modify_y(Segt *tr , int p , LL y) {
        int l = tr->l , r = tr->r;
        int m = (l+r)/2;

        if(l == r) {
                tr->log_y = log(static_cast<double>(y));

                return;
        }

        if(p <= m) modify_y(tr->lc , p , y);
        else modify_y(tr->rc , p , y);

        tr->log_y = max(tr->lc->log_y , tr->rc->log_y);
}

void query_best_ans_pos(Segt *tr , double tmp) {
        if(tr->l == tr->r) {
                if(tmp+tr->log_x+tr->log_y > best_log_ans) {
                        best_log_ans = tmp+tr->log_x+tr->log_y;
                        best_ans_pos = tr->l;
                }

                return;
        }

        query_best_ans_pos(tr->rc , tmp+tr->lc->log_x);

        if(tmp+tr->lc->log_x+tr->lc->log_y > best_log_ans) query_best_ans_pos(tr->lc , tmp);
}

LL query_x(Segt *tr , int p) {
        int l = tr->l , r = tr->r;
        int m = (l+r)/2;
        LL res;

        if(r <= p) return tr->x;

        res = query_x(tr->lc , p);
        if(m+1 <= p) (res *= query_x(tr->rc , p)) %= mod;

        return res;
}

int init(int N , int x[] , int y[]) {
	tr = build(0 , N-1);

	for(int i = 0; i < N; i++) modify_x(tr , i , x[i]);

	for(int i = 0; i < N; i++) {
		Y[i] = static_cast<LL>(y[i]);

		modify_y(tr , i , Y[i]);
	}

	best_ans_pos = 0;
        	best_log_ans = 0.0;

        	query_best_ans_pos(tr , 0.0);

        	return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}

int updateX(int pos , int val) {
	modify_x(tr , pos , static_cast<LL>(val));

	best_ans_pos = 0;
        	best_log_ans = 0.0;

        	query_best_ans_pos(tr , 0.0);

        	return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}

int updateY(int pos , int val) {
	Y[pos] = static_cast<LL>(val);

	modify_y(tr , pos , Y[pos]);

	best_ans_pos = 0;
        	best_log_ans = 0.0;

        	query_best_ans_pos(tr , 0.0);

        	return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}

Subtask #1
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	98856 KB	Output is correct
2	Correct	98856 KB	Output is correct
3	Correct	98856 KB	Output is correct
4	Correct	98856 KB	Output is correct
5	Correct	98856 KB	Output is correct
6	Correct	98856 KB	Output is correct
7	Correct	98856 KB	Output is correct
8	Correct	98856 KB	Output is correct
9	Correct	98856 KB	Output is correct
10	Correct	98856 KB	Output is correct
11	Correct	98856 KB	Output is correct
12	Correct	98856 KB	Output is correct
13	Correct	98856 KB	Output is correct
14	Correct	98856 KB	Output is correct
15	Correct	98856 KB	Output is correct
16	Correct	98856 KB	Output is correct
17	Correct	98856 KB	Output is correct
18	Correct	98856 KB	Output is correct
19	Correct	98856 KB	Output is correct
20	Correct	98856 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	98856 KB	Output is correct
2	Correct	0 ms	98856 KB	Output is correct
3	Correct	0 ms	98856 KB	Output is correct
4	Correct	0 ms	98856 KB	Output is correct
5	Correct	0 ms	98856 KB	Output is correct
6	Correct	0 ms	98856 KB	Output is correct
7	Correct	0 ms	98856 KB	Output is correct
8	Correct	0 ms	98856 KB	Output is correct
9	Correct	0 ms	98856 KB	Output is correct
10	Correct	0 ms	98856 KB	Output is correct
11	Correct	0 ms	98856 KB	Output is correct
12	Correct	0 ms	98856 KB	Output is correct
13	Correct	0 ms	98856 KB	Output is correct
14	Correct	0 ms	98856 KB	Output is correct
15	Correct	0 ms	98856 KB	Output is correct
16	Correct	0 ms	98856 KB	Output is correct
17	Correct	0 ms	98856 KB	Output is correct
18	Correct	0 ms	98856 KB	Output is correct
19	Correct	0 ms	98856 KB	Output is correct
20	Correct	0 ms	98856 KB	Output is correct
21	Correct	0 ms	98856 KB	Output is correct
22	Correct	0 ms	98856 KB	Output is correct
23	Correct	0 ms	98856 KB	Output is correct
24	Correct	0 ms	98856 KB	Output is correct
25	Correct	0 ms	98856 KB	Output is correct
26	Correct	0 ms	98856 KB	Output is correct
27	Correct	0 ms	98856 KB	Output is correct
28	Correct	0 ms	98856 KB	Output is correct
29	Correct	0 ms	98856 KB	Output is correct
30	Correct	1 ms	98856 KB	Output is correct
31	Correct	0 ms	98856 KB	Output is correct
32	Correct	0 ms	98856 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	391 ms	102768 KB	Output is correct
2	Correct	449 ms	102768 KB	Output is correct
3	Correct	422 ms	102768 KB	Output is correct
4	Correct	455 ms	102768 KB	Output is correct

Subtask #4
0.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	98856 KB	Output is correct
2	Correct	0 ms	98856 KB	Output is correct
3	Correct	0 ms	98856 KB	Output is correct
4	Correct	0 ms	98856 KB	Output is correct
5	Correct	0 ms	98856 KB	Output is correct
6	Correct	0 ms	98856 KB	Output is correct
7	Correct	0 ms	98856 KB	Output is correct
8	Correct	0 ms	98856 KB	Output is correct
9	Correct	0 ms	98856 KB	Output is correct
10	Correct	0 ms	98856 KB	Output is correct
11	Correct	0 ms	98856 KB	Output is correct
12	Correct	0 ms	98856 KB	Output is correct
13	Correct	0 ms	98856 KB	Output is correct
14	Correct	0 ms	98856 KB	Output is correct
15	Correct	0 ms	98856 KB	Output is correct
16	Correct	0 ms	98856 KB	Output is correct
17	Correct	0 ms	98856 KB	Output is correct
18	Correct	0 ms	98856 KB	Output is correct
19	Correct	0 ms	98856 KB	Output is correct
20	Correct	0 ms	98856 KB	Output is correct
21	Correct	0 ms	98856 KB	Output is correct
22	Correct	0 ms	98856 KB	Output is correct
23	Correct	0 ms	98856 KB	Output is correct
24	Correct	0 ms	98856 KB	Output is correct
25	Correct	0 ms	98856 KB	Output is correct
26	Correct	0 ms	98856 KB	Output is correct
27	Correct	0 ms	98856 KB	Output is correct
28	Correct	1 ms	98856 KB	Output is correct
29	Correct	1 ms	98856 KB	Output is correct
30	Correct	0 ms	98856 KB	Output is correct
31	Correct	1 ms	98856 KB	Output is correct
32	Correct	0 ms	98856 KB	Output is correct
33	Correct	326 ms	102768 KB	Output is correct
34	Correct	320 ms	102768 KB	Output is correct
35	Correct	343 ms	102768 KB	Output is correct
36	Correct	352 ms	102768 KB	Output is correct
37	Correct	308 ms	102768 KB	Output is correct
38	Correct	318 ms	102768 KB	Output is correct
39	Correct	306 ms	102768 KB	Output is correct
40	Correct	333 ms	102768 KB	Output is correct
41	Correct	313 ms	102768 KB	Output is correct
42	Correct	305 ms	102768 KB	Output is correct
43	Correct	321 ms	102768 KB	Output is correct
44	Incorrect	326 ms	102768 KB	Output isn't correct

Subtask #5
0.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	98856 KB	Output is correct
2	Correct	0 ms	98856 KB	Output is correct
3	Correct	0 ms	98856 KB	Output is correct
4	Correct	0 ms	98856 KB	Output is correct
5	Correct	0 ms	98856 KB	Output is correct
6	Correct	0 ms	98856 KB	Output is correct
7	Correct	0 ms	98856 KB	Output is correct
8	Correct	0 ms	98856 KB	Output is correct
9	Correct	0 ms	98856 KB	Output is correct
10	Correct	0 ms	98856 KB	Output is correct
11	Correct	0 ms	98856 KB	Output is correct
12	Correct	0 ms	98856 KB	Output is correct
13	Correct	0 ms	98856 KB	Output is correct
14	Correct	0 ms	98856 KB	Output is correct
15	Correct	0 ms	98856 KB	Output is correct
16	Correct	0 ms	98856 KB	Output is correct
17	Correct	0 ms	98856 KB	Output is correct
18	Correct	0 ms	98856 KB	Output is correct
19	Correct	0 ms	98856 KB	Output is correct
20	Correct	0 ms	98856 KB	Output is correct
21	Correct	0 ms	98856 KB	Output is correct
22	Correct	0 ms	98856 KB	Output is correct
23	Correct	0 ms	98856 KB	Output is correct
24	Correct	0 ms	98856 KB	Output is correct
25	Correct	1 ms	98856 KB	Output is correct
26	Correct	0 ms	98856 KB	Output is correct
27	Correct	2 ms	98856 KB	Output is correct
28	Correct	1 ms	98856 KB	Output is correct
29	Correct	1 ms	98856 KB	Output is correct
30	Correct	0 ms	98856 KB	Output is correct
31	Correct	1 ms	98856 KB	Output is correct
32	Correct	0 ms	98856 KB	Output is correct
33	Correct	384 ms	102768 KB	Output is correct
34	Correct	446 ms	102768 KB	Output is correct
35	Correct	410 ms	102768 KB	Output is correct
36	Correct	446 ms	102768 KB	Output is correct
37	Correct	356 ms	102768 KB	Output is correct
38	Correct	321 ms	102768 KB	Output is correct
39	Correct	399 ms	102768 KB	Output is correct
40	Correct	392 ms	102768 KB	Output is correct
41	Correct	302 ms	102768 KB	Output is correct
42	Correct	323 ms	102768 KB	Output is correct
43	Correct	298 ms	102768 KB	Output is correct
44	Correct	359 ms	102768 KB	Output is correct
45	Correct	309 ms	102768 KB	Output is correct
46	Correct	307 ms	102768 KB	Output is correct
47	Correct	326 ms	102768 KB	Output is correct
48	Incorrect	307 ms	102768 KB	Output isn't correct
49	Halted	0 ms	0 KB	-

답안 #17428

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 0.0 / 23.0

Subtask #5 0.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
0.0 / 23.0

Subtask #5
0.0 / 23.0