답안 #30831 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30831	2017-07-27T10:20:19 Z	inqr	말 (IOI15_horses)	C++14	100 / 100	1263 ms	76264 KB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define pii pair < int , int >
#define DB printf("debug\n");
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define all(x) x.begin() , x.end()
#define MAXN 500005
#define MOD (ll)1000000007
using namespace std;
int n;
ll x[MAXN],y[MAXN];
pair<double,ll> st[4*MAXN];
pair<double,ll> lz[4*MAXN];

pair<double,ll> merge(pair<double,ll> a,pair<double,ll> b){
	return {a.st+b.st,(a.nd*b.nd+MOD)%MOD};
}

void lz_upd(int l,int r,int stp){
	st[stp]=merge(st[stp],lz[stp]);
	if(l!=r){
		lz[stp*2]=merge(lz[stp*2],lz[stp]);
		lz[stp*2+1]=merge(lz[stp*2+1],lz[stp]);
	}
	lz[stp]={0,1};
}

void upd(int ul,int ur,double uv1,ll uv2,int l,int r,int stp){
	lz_upd(l,r,stp);
	if(l>r||ur<l||r<ul)return;
	if(ul<=l&&r<=ur){
		lz[stp]={uv1,uv2};
		lz_upd(l,r,stp);
		return;
	}
	int m=(l+r)/2;
	upd(ul,ur,uv1,uv2,l,m,stp*2);upd(ul,ur,uv1,uv2,m+1,r,stp*2+1);
	st[stp]=max(st[stp*2],st[stp*2+1]);
}

void build(int l,int r,int stp){
	if(l>r)return;
	if(l==r){
		st[stp]=lz[stp]={0,1};
		return;
	}
	st[stp]=lz[stp]={0,1};
	int m=(l+r)/2;
	build(l,m,stp*2);build(m+1,r,stp*2+1);
}
ll invert(ll base){
	ll res=1;
	ll exp=MOD-2;
	while(exp>0){
		if(exp&1){
			res*=base;
			res%=MOD;
		}
		base*=base;
		base%=MOD;
		exp/=2;
	}
	return res;
}
int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<n;i++)x[i]=X[i],y[i]=Y[i];
	build(0,n-1,1);
	for(int i=0;i<n;i++){
		upd(i,n-1,(double)log2(x[i]),x[i],0,n-1,1);
		upd(i,i,(double)log2(y[i]),y[i],0,n-1,1);
	}
	return st[1].nd;
}
int updateX(int pos, int val){	
	upd(pos,n-1,-(double)log2(x[pos]),invert(x[pos]),0,n-1,1);
	x[pos]=val;
	upd(pos,n-1,(double)log2(x[pos]),x[pos],0,n-1,1);
	return st[1].nd;
}
int updateY(int pos, int val) {
	upd(pos,pos,-(double)log2(y[pos]),invert(y[pos]),0,n-1,1);
	y[pos]=val;
	upd(pos,pos,(double)log2(y[pos]),y[pos],0,n-1,1);
	return st[1].nd;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:7:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define nd second
            ^
horses.cpp:80:15: note: in expansion of macro 'nd'
  return st[1].nd;
               ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:7:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define nd second
            ^
horses.cpp:86:15: note: in expansion of macro 'nd'
  return st[1].nd;
               ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:7:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define nd second
            ^
horses.cpp:92:15: note: in expansion of macro 'nd'
  return st[1].nd;
               ^

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	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
21	Correct	72352 KB	Output is correct
22	Correct	72352 KB	Output is correct
23	Correct	72352 KB	Output is correct
24	Correct	72352 KB	Output is correct
25	Correct	72352 KB	Output is correct
26	Correct	72352 KB	Output is correct
27	Correct	72352 KB	Output is correct
28	Correct	72352 KB	Output is correct
29	Correct	72352 KB	Output is correct
30	Correct	72352 KB	Output is correct
31	Correct	72352 KB	Output is correct
32	Correct	72352 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1049 ms	76264 KB	Output is correct
2	Correct	1226 ms	76264 KB	Output is correct
3	Correct	1143 ms	76264 KB	Output is correct
4	Correct	1163 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	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	0 ms	72352 KB	Output is correct
30	Correct	0 ms	72352 KB	Output is correct
31	Correct	3 ms	72352 KB	Output is correct
32	Correct	0 ms	72352 KB	Output is correct
33	Correct	943 ms	76264 KB	Output is correct
34	Correct	833 ms	76264 KB	Output is correct
35	Correct	933 ms	76264 KB	Output is correct
36	Correct	846 ms	76264 KB	Output is correct
37	Correct	903 ms	76264 KB	Output is correct
38	Correct	876 ms	76264 KB	Output is correct
39	Correct	843 ms	76264 KB	Output is correct
40	Correct	866 ms	76264 KB	Output is correct
41	Correct	853 ms	76264 KB	Output is correct
42	Correct	823 ms	76264 KB	Output is correct
43	Correct	819 ms	76264 KB	Output is correct
44	Correct	809 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	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	3 ms	72352 KB	Output is correct
29	Correct	3 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	1086 ms	76264 KB	Output is correct
34	Correct	1216 ms	76264 KB	Output is correct
35	Correct	1143 ms	76264 KB	Output is correct
36	Correct	1069 ms	76264 KB	Output is correct
37	Correct	823 ms	76264 KB	Output is correct
38	Correct	856 ms	76264 KB	Output is correct
39	Correct	786 ms	76264 KB	Output is correct
40	Correct	856 ms	76264 KB	Output is correct
41	Correct	856 ms	76264 KB	Output is correct
42	Correct	839 ms	76264 KB	Output is correct
43	Correct	873 ms	76264 KB	Output is correct
44	Correct	869 ms	76264 KB	Output is correct
45	Correct	826 ms	76264 KB	Output is correct
46	Correct	829 ms	76264 KB	Output is correct
47	Correct	769 ms	76264 KB	Output is correct
48	Correct	866 ms	76264 KB	Output is correct
49	Correct	1263 ms	76264 KB	Output is correct
50	Correct	1256 ms	76264 KB	Output is correct
51	Correct	1079 ms	76264 KB	Output is correct
52	Correct	1012 ms	76264 KB	Output is correct
53	Correct	1196 ms	76264 KB	Output is correct
54	Correct	1143 ms	76264 KB	Output is correct
55	Correct	936 ms	76264 KB	Output is correct
56	Correct	963 ms	76264 KB	Output is correct
57	Correct	943 ms	76264 KB	Output is correct
58	Correct	946 ms	76264 KB	Output is correct
59	Correct	866 ms	76264 KB	Output is correct

답안 #30831

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