답안 #828847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828847	2023-08-17T17:32:05 Z	bachhoangxuan	말 (IOI15_horses)	C++17	100 / 100	202 ms	103908 KB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e9+1;
const ll mod=1e9+7;
const int maxn = 5e5+5;
ll mul(ll a,ll b){
    return min(a*b,inf);
}
ll n,x[maxn],y[maxn];
struct node{
    ll p,pre,suf;
    ll pm,sm;
    node(ll pos=0):p(pos){
        pre=pm=x[p];
        suf=sm=1;
    }
    friend node operator+(node a,node b){
        node res;
        ll mm=mul(a.suf,b.pre);
        if(y[a.p]>mul(mm,y[b.p])){
            res.p=a.p;
            res.pre=a.pre;res.pm=a.pm;
            res.suf=mul(a.suf,mul(b.pre,b.suf));
            res.sm=a.sm*b.pm%mod*b.sm%mod;
        }
        else{
            res.p=b.p;
            res.suf=b.suf;res.sm=b.sm;
            res.pre=mul(b.pre,mul(a.pre,a.suf));
            res.pm=b.pm*a.pm%mod*a.sm%mod;
        }
        return res;
    }
};

node tree[4*maxn];
void update(int l,int r,int id,int p){
    if(l==r){
        tree[id]=node(l);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(l,mid,id<<1,p);
    else update(mid+1,r,id<<1|1,p);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}
void build(int l,int r,int id){
    if(l==r){
        tree[id]=node(l);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}

int init(int N, int X[], int Y[]) {
    n=N;
    for(int i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1];
    build(1,n,1);
    return tree[1].pm*y[tree[1].p]%mod;
}

int updateX(int pos, int val) {
    x[pos+1]=val;
    update(1,n,1,pos+1);
    return tree[1].pm*y[tree[1].p]%mod;
}

int updateY(int pos, int val) {
    y[pos+1]=val;
    update(1,n,1,pos+1);
    //cout << tree[1].p << '\n';
    return tree[1].pm*y[tree[1].p]%mod;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:62:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |     build(1,n,1);
      |             ^
horses.cpp:63:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |     return tree[1].pm*y[tree[1].p]%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:68:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |     update(1,n,1,pos+1);
      |              ^
horses.cpp:69:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |     return tree[1].pm*y[tree[1].p]%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:74:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |     update(1,n,1,pos+1);
      |              ^
horses.cpp:76:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |     return tree[1].pm*y[tree[1].p]%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	78576 KB	Output is correct
2	Correct	31 ms	78560 KB	Output is correct
3	Correct	31 ms	78524 KB	Output is correct
4	Correct	30 ms	78580 KB	Output is correct
5	Correct	31 ms	78576 KB	Output is correct
6	Correct	31 ms	78544 KB	Output is correct
7	Correct	30 ms	78556 KB	Output is correct
8	Correct	32 ms	78544 KB	Output is correct
9	Correct	32 ms	78568 KB	Output is correct
10	Correct	31 ms	78484 KB	Output is correct
11	Correct	30 ms	78552 KB	Output is correct
12	Correct	33 ms	78476 KB	Output is correct
13	Correct	33 ms	78508 KB	Output is correct
14	Correct	34 ms	78468 KB	Output is correct
15	Correct	32 ms	78540 KB	Output is correct
16	Correct	31 ms	78472 KB	Output is correct
17	Correct	30 ms	78484 KB	Output is correct
18	Correct	33 ms	78512 KB	Output is correct
19	Correct	31 ms	78528 KB	Output is correct
20	Correct	31 ms	78560 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	78540 KB	Output is correct
2	Correct	39 ms	78496 KB	Output is correct
3	Correct	32 ms	78584 KB	Output is correct
4	Correct	31 ms	78492 KB	Output is correct
5	Correct	34 ms	78584 KB	Output is correct
6	Correct	30 ms	78548 KB	Output is correct
7	Correct	32 ms	78548 KB	Output is correct
8	Correct	32 ms	78540 KB	Output is correct
9	Correct	31 ms	78548 KB	Output is correct
10	Correct	39 ms	78464 KB	Output is correct
11	Correct	32 ms	78544 KB	Output is correct
12	Correct	30 ms	78584 KB	Output is correct
13	Correct	33 ms	78480 KB	Output is correct
14	Correct	32 ms	78484 KB	Output is correct
15	Correct	41 ms	78556 KB	Output is correct
16	Correct	40 ms	78536 KB	Output is correct
17	Correct	32 ms	78540 KB	Output is correct
18	Correct	31 ms	78548 KB	Output is correct
19	Correct	30 ms	78528 KB	Output is correct
20	Correct	39 ms	78568 KB	Output is correct
21	Correct	34 ms	78540 KB	Output is correct
22	Correct	34 ms	78496 KB	Output is correct
23	Correct	33 ms	78556 KB	Output is correct
24	Correct	36 ms	78540 KB	Output is correct
25	Correct	38 ms	78528 KB	Output is correct
26	Correct	33 ms	78580 KB	Output is correct
27	Correct	35 ms	78596 KB	Output is correct
28	Correct	36 ms	78588 KB	Output is correct
29	Correct	35 ms	78608 KB	Output is correct
30	Correct	33 ms	78628 KB	Output is correct
31	Correct	33 ms	78576 KB	Output is correct
32	Correct	40 ms	78600 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	102 ms	91296 KB	Output is correct
2	Correct	202 ms	103908 KB	Output is correct
3	Correct	155 ms	95036 KB	Output is correct
4	Correct	168 ms	98932 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	78492 KB	Output is correct
2	Correct	32 ms	78472 KB	Output is correct
3	Correct	32 ms	78480 KB	Output is correct
4	Correct	32 ms	78528 KB	Output is correct
5	Correct	33 ms	78572 KB	Output is correct
6	Correct	33 ms	78564 KB	Output is correct
7	Correct	38 ms	78556 KB	Output is correct
8	Correct	36 ms	78532 KB	Output is correct
9	Correct	32 ms	78500 KB	Output is correct
10	Correct	31 ms	78560 KB	Output is correct
11	Correct	30 ms	78580 KB	Output is correct
12	Correct	30 ms	78564 KB	Output is correct
13	Correct	33 ms	78532 KB	Output is correct
14	Correct	37 ms	78492 KB	Output is correct
15	Correct	32 ms	78560 KB	Output is correct
16	Correct	37 ms	78532 KB	Output is correct
17	Correct	30 ms	78552 KB	Output is correct
18	Correct	33 ms	78480 KB	Output is correct
19	Correct	34 ms	78480 KB	Output is correct
20	Correct	33 ms	78508 KB	Output is correct
21	Correct	36 ms	78548 KB	Output is correct
22	Correct	37 ms	78568 KB	Output is correct
23	Correct	39 ms	78620 KB	Output is correct
24	Correct	31 ms	78592 KB	Output is correct
25	Correct	31 ms	78544 KB	Output is correct
26	Correct	40 ms	78584 KB	Output is correct
27	Correct	33 ms	78600 KB	Output is correct
28	Correct	39 ms	78532 KB	Output is correct
29	Correct	37 ms	78520 KB	Output is correct
30	Correct	36 ms	78552 KB	Output is correct
31	Correct	34 ms	78564 KB	Output is correct
32	Correct	31 ms	78548 KB	Output is correct
33	Correct	73 ms	94280 KB	Output is correct
34	Correct	70 ms	94248 KB	Output is correct
35	Correct	86 ms	101280 KB	Output is correct
36	Correct	87 ms	101216 KB	Output is correct
37	Correct	67 ms	92428 KB	Output is correct
38	Correct	59 ms	93308 KB	Output is correct
39	Correct	68 ms	92368 KB	Output is correct
40	Correct	72 ms	96240 KB	Output is correct
41	Correct	55 ms	92428 KB	Output is correct
42	Correct	52 ms	92432 KB	Output is correct
43	Correct	68 ms	96692 KB	Output is correct
44	Correct	73 ms	96620 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	78464 KB	Output is correct
2	Correct	28 ms	78572 KB	Output is correct
3	Correct	31 ms	78548 KB	Output is correct
4	Correct	32 ms	78564 KB	Output is correct
5	Correct	31 ms	78584 KB	Output is correct
6	Correct	35 ms	78540 KB	Output is correct
7	Correct	31 ms	78548 KB	Output is correct
8	Correct	30 ms	78496 KB	Output is correct
9	Correct	29 ms	78472 KB	Output is correct
10	Correct	28 ms	78572 KB	Output is correct
11	Correct	32 ms	78600 KB	Output is correct
12	Correct	38 ms	78528 KB	Output is correct
13	Correct	38 ms	78540 KB	Output is correct
14	Correct	32 ms	78580 KB	Output is correct
15	Correct	30 ms	78540 KB	Output is correct
16	Correct	29 ms	78548 KB	Output is correct
17	Correct	30 ms	78504 KB	Output is correct
18	Correct	29 ms	78508 KB	Output is correct
19	Correct	31 ms	78488 KB	Output is correct
20	Correct	32 ms	78476 KB	Output is correct
21	Correct	33 ms	78588 KB	Output is correct
22	Correct	33 ms	78576 KB	Output is correct
23	Correct	33 ms	78552 KB	Output is correct
24	Correct	30 ms	78592 KB	Output is correct
25	Correct	36 ms	78568 KB	Output is correct
26	Correct	31 ms	78624 KB	Output is correct
27	Correct	51 ms	78520 KB	Output is correct
28	Correct	40 ms	78592 KB	Output is correct
29	Correct	37 ms	78536 KB	Output is correct
30	Correct	31 ms	78540 KB	Output is correct
31	Correct	32 ms	78504 KB	Output is correct
32	Correct	32 ms	78600 KB	Output is correct
33	Correct	93 ms	95096 KB	Output is correct
34	Correct	187 ms	103804 KB	Output is correct
35	Correct	166 ms	95100 KB	Output is correct
36	Correct	176 ms	98892 KB	Output is correct
37	Correct	87 ms	94308 KB	Output is correct
38	Correct	70 ms	94332 KB	Output is correct
39	Correct	84 ms	101252 KB	Output is correct
40	Correct	85 ms	101156 KB	Output is correct
41	Correct	77 ms	92492 KB	Output is correct
42	Correct	61 ms	93372 KB	Output is correct
43	Correct	56 ms	92364 KB	Output is correct
44	Correct	69 ms	96260 KB	Output is correct
45	Correct	65 ms	92428 KB	Output is correct
46	Correct	60 ms	92460 KB	Output is correct
47	Correct	72 ms	96704 KB	Output is correct
48	Correct	70 ms	96644 KB	Output is correct
49	Correct	149 ms	96268 KB	Output is correct
50	Correct	160 ms	96276 KB	Output is correct
51	Correct	121 ms	103072 KB	Output is correct
52	Correct	138 ms	102632 KB	Output is correct
53	Correct	139 ms	94708 KB	Output is correct
54	Correct	98 ms	95164 KB	Output is correct
55	Correct	89 ms	93472 KB	Output is correct
56	Correct	105 ms	98084 KB	Output is correct
57	Correct	87 ms	93988 KB	Output is correct
58	Correct	88 ms	94512 KB	Output is correct
59	Correct	67 ms	96640 KB	Output is correct