oj.uz

답안 #213121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213121 2020-03-25T03:24:41 Z KoalaMuch 말 (IOI15_horses) C++14
100 / 100
 1201 ms 50296 KB 
#include "horses.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
long long sm[2000005]; //return index of best value
pair< long long,long long > sm2[2000005]; //quick multiply
long long x[500005];
long long y[500005];
long long n;
void up2(long long l,long long r,long long idx,long long now)
{
    if(l>idx||r<idx)    return;
    if(l==r)    {sm2[now].first = x[l];return;}
    long long mid = (l+r) >> 1;
    up2(l,mid,idx,now<<1),up2(mid+1,r,idx,now<<1|1);
    long long v = sm2[now<<1].first*sm2[now<<1|1].first;
    sm2[now] = {v%mod,sm2[now<<1].second||sm2[now<<1|1].second||v>=mod};
}
pair< long long,long long > GetQMul(long long l,long long r,long long ll,long long rr,long long now)
{
    if(l>rr||r<ll)  return {1ll,0ll};
    if(l>=ll&&r<=rr)    return sm2[now];
    long long mid = (l+r) >> 1;
    pair< long long,long long > a = GetQMul(l,mid,ll,rr,now<<1),b = GetQMul(mid+1,r,ll,rr,now<<1|1);
    long long v = a.first*b.first;
    return {v%mod,a.second||b.second||v>=mod};
}
long long comp(long long i,long long j)
{
    long long want = (y[i]+y[j]-1)/y[j];
    pair< long long,long long > a = GetQMul(1,n,i+1,j,1);
    if(a.second==1||a.first>=want)  return j;
    return i;
}
void up1(long long l,long long r,long long idx,long long now)
{
    if(l>idx||r<idx)    return ;
    if(l==r)    {sm[now] = l;return;}
    long long mid = (l+r) >> 1;
    up1(l,mid,idx,now<<1),up1(mid+1,r,idx,now<<1|1);
    if(sm[now<<1]&&sm[now<<1|1])sm[now] = comp(sm[now<<1],sm[now<<1|1]);
}
int init(int N, int X[], int Y[]) {
    n = N;
    for(long long i=0;i<N;i++)    x[i+1] = X[i],y[i+1] = Y[i];
    for(long long i=1;i<=n;i++)   up2(1,n,i,1);
    for(long long i=1;i<=n;i++)   up1(1,n,i,1);
	return GetQMul(1,n,1,sm[1],1).first*y[sm[1]]%mod;
}
int updateX(int pos, int val) {
    x[pos+1] = val;
    up2(1,n,pos+1,1);
    up1(1,n,pos+1,1);
	return GetQMul(1,n,1,sm[1],1).first*y[sm[1]]%mod;
}
int updateY(int pos, int val) {
    y[pos+1] = val;
    up1(1,n,pos+1,1);
	return GetQMul(1,n,1,sm[1],1).first*y[sm[1]]%mod;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:49:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return GetQMul(1,n,1,sm[1],1).first*y[sm[1]]%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:55:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return GetQMul(1,n,1,sm[1],1).first*y[sm[1]]%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:60:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return GetQMul(1,n,1,sm[1],1).first*y[sm[1]]%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 799 ms 41592 KB Output is correct
2 Correct 814 ms 50296 KB Output is correct
3 Correct 965 ms 41464 KB Output is correct
4 Correct 875 ms 45432 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 7 ms 512 KB Output is correct
24 Correct 7 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 7 ms 512 KB Output is correct
28 Correct 7 ms 512 KB Output is correct
29 Correct 8 ms 512 KB Output is correct
30 Correct 6 ms 384 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 6 ms 512 KB Output is correct
33 Correct 469 ms 40824 KB Output is correct
34 Correct 476 ms 40824 KB Output is correct
35 Correct 465 ms 47736 KB Output is correct
36 Correct 437 ms 47736 KB Output is correct
37 Correct 421 ms 38904 KB Output is correct
38 Correct 421 ms 39800 KB Output is correct
39 Correct 382 ms 38776 KB Output is correct
40 Correct 414 ms 42744 KB Output is correct
41 Correct 373 ms 38904 KB Output is correct
42 Correct 413 ms 38904 KB Output is correct
43 Correct 399 ms 43128 KB Output is correct
44 Correct 401 ms 43128 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 7 ms 512 KB Output is correct
24 Correct 8 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 6 ms 512 KB Output is correct
28 Correct 6 ms 512 KB Output is correct
29 Correct 6 ms 512 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 7 ms 512 KB Output is correct
33 Correct 826 ms 41604 KB Output is correct
34 Correct 810 ms 50296 KB Output is correct
35 Correct 944 ms 41464 KB Output is correct
36 Correct 977 ms 45432 KB Output is correct
37 Correct 493 ms 40824 KB Output is correct
38 Correct 472 ms 40824 KB Output is correct
39 Correct 441 ms 47736 KB Output is correct
40 Correct 405 ms 47608 KB Output is correct
41 Correct 405 ms 38904 KB Output is correct
42 Correct 422 ms 39800 KB Output is correct
43 Correct 373 ms 38776 KB Output is correct
44 Correct 419 ms 42744 KB Output is correct
45 Correct 384 ms 38904 KB Output is correct
46 Correct 404 ms 38904 KB Output is correct
47 Correct 370 ms 43128 KB Output is correct
48 Correct 394 ms 43128 KB Output is correct
49 Correct 1201 ms 42744 KB Output is correct
50 Correct 1108 ms 42744 KB Output is correct
51 Correct 813 ms 49528 KB Output is correct
52 Correct 617 ms 49144 KB Output is correct
53 Correct 999 ms 41080 KB Output is correct
54 Correct 804 ms 41720 KB Output is correct
55 Correct 594 ms 39928 KB Output is correct
56 Correct 660 ms 44536 KB Output is correct
57 Correct 729 ms 40568 KB Output is correct
58 Correct 774 ms 41080 KB Output is correct
59 Correct 358 ms 43128 KB Output is correct