답안 #28072 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28072	2017-07-15T07:34:05 Z	top34051	말 (IOI15_horses)	C++14	100 / 100	1153 ms	76264 KB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
#define pdl pair<double,long long>
#define mod (long long)1000000007

int n;
long long a[maxn];
long long b[maxn];
pdl tree[maxn*4];
pdl lazy[maxn*4];

pdl fus(pdl x,pdl y) {
    return {x.first+y.first,(x.second*y.second+mod)%mod};
}

long long inv(long long value){
    if(value == 1) return 1;
    long long tmp = (inv(mod%value)*((-mod)/value));
    tmp %= mod;
    if(tmp < 0) tmp += mod;
    return tmp;
}

void upd(int now,int l,int r) {
    tree[now] = fus(tree[now],lazy[now]);
    if(l!=r) {
        lazy[now<<1] = fus(lazy[now<<1],lazy[now]);
        lazy[now<<1|1] = fus(lazy[now<<1|1],lazy[now]);
    }
    lazy[now] = {0,1};
}

void update(int now,int l,int r,int x,int y,double val1,long long val2) {
    upd(now,l,r);
    if(l>r || l>y || r<x) return ;
    if(x<=l && r<=y) {
        lazy[now] = {val1,val2};
        upd(now,l,r);
        return ;
    }
    int mid = (l+r)/2;
    update(now<<1,l,mid,x,y,val1,val2); update(now<<1|1,mid+1,r,x,y,val1,val2);
    tree[now] = max(tree[now<<1],tree[now<<1|1]);
}

void build(int now,int l,int r) {
    if(l==r) {
        tree[now] = lazy[now] = {0,1};
        return ;
    }
    int mid = (l+r)/2;
    build(now<<1,l,mid); build(now<<1|1,mid+1,r);
    tree[now] = lazy[now] = {0,1};
}

int init(int N, int X[], int Y[]) {
    n = N;
    for(int i=0;i<n;i++) a[i] = X[i], b[i] = Y[i];
    build(1,0,n-1);
    for(int i=0;i<n;i++) update(1,0,n-1,i,n-1,(double)log2(a[i]),a[i]);
    for(int i=0;i<n;i++) update(1,0,n-1,i,i,(double)log2(b[i]),b[i]);
	return tree[1].second;
}

int updateX(int pos, int val) {
    update(1,0,n-1,pos,n-1,-(double)log2(a[pos]),inv(a[pos]));
    a[pos] = val;
	update(1,0,n-1,pos,n-1,(double)log2(a[pos]),a[pos]);
	return tree[1].second;
}

int updateY(int pos, int val) {
    update(1,0,n-1,pos,pos,-(double)log2(b[pos]),inv(b[pos]));
    b[pos] = val;
	update(1,0,n-1,pos,pos,(double)log2(b[pos]),b[pos]);
	return tree[1].second;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:64:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return tree[1].second;
                 ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:71:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return tree[1].second;
                 ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:78:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return tree[1].second;
                 ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1053 ms	76264 KB	Output is correct
2	Correct	1079 ms	76264 KB	Output is correct
3	Correct	1046 ms	76264 KB	Output is correct
4	Correct	1153 ms	76264 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	72352 KB	Output is correct
2	Correct	0 ms	72352 KB	Output is correct
3	Correct	0 ms	72352 KB	Output is correct
4	Correct	0 ms	72352 KB	Output is correct
5	Correct	0 ms	72352 KB	Output is correct
6	Correct	0 ms	72352 KB	Output is correct
7	Correct	0 ms	72352 KB	Output is correct
8	Correct	0 ms	72352 KB	Output is correct
9	Correct	0 ms	72352 KB	Output is correct
10	Correct	0 ms	72352 KB	Output is correct
11	Correct	0 ms	72352 KB	Output is correct
12	Correct	0 ms	72352 KB	Output is correct
13	Correct	0 ms	72352 KB	Output is correct
14	Correct	0 ms	72352 KB	Output is correct
15	Correct	0 ms	72352 KB	Output is correct
16	Correct	0 ms	72352 KB	Output is correct
17	Correct	0 ms	72352 KB	Output is correct
18	Correct	0 ms	72352 KB	Output is correct
19	Correct	0 ms	72352 KB	Output is correct
20	Correct	0 ms	72352 KB	Output is correct
21	Correct	0 ms	72352 KB	Output is correct
22	Correct	0 ms	72352 KB	Output is correct
23	Correct	0 ms	72352 KB	Output is correct
24	Correct	3 ms	72352 KB	Output is correct
25	Correct	0 ms	72352 KB	Output is correct
26	Correct	0 ms	72352 KB	Output is correct
27	Correct	3 ms	72352 KB	Output is correct
28	Correct	0 ms	72352 KB	Output is correct
29	Correct	0 ms	72352 KB	Output is correct
30	Correct	3 ms	72352 KB	Output is correct
31	Correct	0 ms	72352 KB	Output is correct
32	Correct	0 ms	72352 KB	Output is correct
33	Correct	803 ms	76264 KB	Output is correct
34	Correct	803 ms	76264 KB	Output is correct
35	Correct	783 ms	76264 KB	Output is correct
36	Correct	836 ms	76264 KB	Output is correct
37	Correct	769 ms	76264 KB	Output is correct
38	Correct	806 ms	76264 KB	Output is correct
39	Correct	796 ms	76264 KB	Output is correct
40	Correct	923 ms	76264 KB	Output is correct
41	Correct	796 ms	76264 KB	Output is correct
42	Correct	819 ms	76264 KB	Output is correct
43	Correct	839 ms	76264 KB	Output is correct
44	Correct	773 ms	76264 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	72352 KB	Output is correct
2	Correct	0 ms	72352 KB	Output is correct
3	Correct	0 ms	72352 KB	Output is correct
4	Correct	0 ms	72352 KB	Output is correct
5	Correct	0 ms	72352 KB	Output is correct
6	Correct	0 ms	72352 KB	Output is correct
7	Correct	0 ms	72352 KB	Output is correct
8	Correct	0 ms	72352 KB	Output is correct
9	Correct	0 ms	72352 KB	Output is correct
10	Correct	0 ms	72352 KB	Output is correct
11	Correct	0 ms	72352 KB	Output is correct
12	Correct	0 ms	72352 KB	Output is correct
13	Correct	0 ms	72352 KB	Output is correct
14	Correct	0 ms	72352 KB	Output is correct
15	Correct	0 ms	72352 KB	Output is correct
16	Correct	0 ms	72352 KB	Output is correct
17	Correct	0 ms	72352 KB	Output is correct
18	Correct	0 ms	72352 KB	Output is correct
19	Correct	0 ms	72352 KB	Output is correct
20	Correct	0 ms	72352 KB	Output is correct
21	Correct	0 ms	72352 KB	Output is correct
22	Correct	0 ms	72352 KB	Output is correct
23	Correct	0 ms	72352 KB	Output is correct
24	Correct	3 ms	72352 KB	Output is correct
25	Correct	0 ms	72352 KB	Output is correct
26	Correct	0 ms	72352 KB	Output is correct
27	Correct	3 ms	72352 KB	Output is correct
28	Correct	0 ms	72352 KB	Output is correct
29	Correct	0 ms	72352 KB	Output is correct
30	Correct	3 ms	72352 KB	Output is correct
31	Correct	0 ms	72352 KB	Output is correct
32	Correct	0 ms	72352 KB	Output is correct
33	Correct	996 ms	76264 KB	Output is correct
34	Correct	1109 ms	76264 KB	Output is correct
35	Correct	1008 ms	76264 KB	Output is correct
36	Correct	1026 ms	76264 KB	Output is correct
37	Correct	783 ms	76264 KB	Output is correct
38	Correct	829 ms	76264 KB	Output is correct
39	Correct	789 ms	76264 KB	Output is correct
40	Correct	836 ms	76264 KB	Output is correct
41	Correct	836 ms	76264 KB	Output is correct
42	Correct	816 ms	76264 KB	Output is correct
43	Correct	849 ms	76264 KB	Output is correct
44	Correct	826 ms	76264 KB	Output is correct
45	Correct	806 ms	76264 KB	Output is correct
46	Correct	779 ms	76264 KB	Output is correct
47	Correct	759 ms	76264 KB	Output is correct
48	Correct	786 ms	76264 KB	Output is correct
49	Correct	1086 ms	76264 KB	Output is correct
50	Correct	1018 ms	76264 KB	Output is correct
51	Correct	999 ms	76264 KB	Output is correct
52	Correct	1008 ms	76264 KB	Output is correct
53	Correct	1076 ms	76264 KB	Output is correct
54	Correct	1079 ms	76264 KB	Output is correct
55	Correct	939 ms	76264 KB	Output is correct
56	Correct	1036 ms	76264 KB	Output is correct
57	Correct	1008 ms	76264 KB	Output is correct
58	Correct	903 ms	76264 KB	Output is correct
59	Correct	766 ms	76264 KB	Output is correct

답안 #28072

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 23.0 / 23.0

Subtask #5 23.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
23.0 / 23.0

Subtask #5
23.0 / 23.0