oj.uz

Submission #206303

# Submission time Handle Problem Language Result Execution time Memory
206303 2020-03-03T00:45:03 Z oko Horses (IOI15_horses) C++14
54 / 100
 1500 ms 23544 KB 
#include "horses.h"
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
long long n,a[500500],b[500500],mod=1e9+7,tree[2005000];
long long qrx(int nod,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return tree[nod];
    else if(r<x||y<l)return 1ll;
    int mid=(l+r)/2;
    return (qrx(nod*2,l,mid,x,y)*qrx(nod*2+1,mid+1,r,x,y))%mod;
}
void upx(int nod,int l,int r,int x,long long val)
{
    if(x<l||r<x)return;
    if(l==r)
    {
        tree[nod]=val;
        return;
    }
    int mid=(l+r)/2;
    upx(nod*2,l,mid,x,val);
    upx(nod*2+1,mid+1,r,x,val);
    tree[nod]=(tree[nod*2]*tree[nod*2+1])%mod;
}
long long slov()
{
    long long x=1,ans=0,st;
    for(int i=n-1;i>=0;i--)
    {
        x*=a[i];
        if(x>(long long)2e9)break;
        st=i;
    }
    if(st)ans=b[st-1];
    x=1;
    for(int i=st;i<n;i++)
    {
        x*=a[i];
        ans=max(ans,x*b[i]);
    }
    ans%=mod;
    ans*=qrx(1,0,n+5,0,st-1);
    return ans%mod;
}
int init(int N, int X[], int Y[])
{
    n=N;
    for(int i=0;i<n;i++)
    {
        a[i]=X[i];
        upx(1,0,n+5,i,a[i]);
        b[i]=Y[i];
    }
    return slov();
}
int updateX(int pos, int val)
{
    a[pos]=val;
    upx(1,0,n+5,pos,val);
    return slov();
}
int updateY(int pos, int val)
{
    b[pos]=val;
    return slov();
}

Compilation message

horses.cpp: In function 'long long int slov()':
horses.cpp:30:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     for(int i=n-1;i>=0;i--)
               ~^~
horses.cpp:38:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     for(int i=st;i<n;i++)
               ^~
horses.cpp:44:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     ans*=qrx(1,0,n+5,0,st-1);
                  ~^~
horses.cpp:44:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     ans*=qrx(1,0,n+5,0,st-1);
                        ~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:53:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         upx(1,0,n+5,i,a[i]);
                 ~^~
horses.cpp:56:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return slov();
            ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:61:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     upx(1,0,n+5,pos,val);
             ~^~
horses.cpp:62:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return slov();
            ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:67:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return slov();
            ~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 380 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 380 KB Output is correct
27 Correct 6 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 8 ms 376 KB Output is correct
30 Correct 6 ms 376 KB Output is correct
31 Correct 8 ms 376 KB Output is correct
32 Correct 7 ms 504 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 21340 KB Output is correct
2 Correct 267 ms 21240 KB Output is correct
3 Correct 227 ms 23288 KB Output is correct
4 Correct 274 ms 23348 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 4 ms 376 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 4 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 4 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 7 ms 380 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 8 ms 376 KB Output is correct
30 Correct 6 ms 376 KB Output is correct
31 Correct 7 ms 376 KB Output is correct
32 Correct 8 ms 376 KB Output is correct
33 Correct 246 ms 20356 KB Output is correct
34 Correct 172 ms 22456 KB Output is correct
35 Correct 197 ms 22392 KB Output is correct
36 Correct 195 ms 22648 KB Output is correct
37 Correct 735 ms 22520 KB Output is correct
38 Correct 155 ms 22540 KB Output is correct
39 Execution timed out 1579 ms 22392 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 380 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 380 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 5 ms 380 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 372 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 6 ms 376 KB Output is correct
27 Correct 6 ms 376 KB Output is correct
28 Correct 5 ms 380 KB Output is correct
29 Correct 8 ms 376 KB Output is correct
30 Correct 6 ms 376 KB Output is correct
31 Correct 8 ms 376 KB Output is correct
32 Correct 8 ms 376 KB Output is correct
33 Correct 201 ms 22776 KB Output is correct
34 Correct 271 ms 23352 KB Output is correct
35 Correct 222 ms 23416 KB Output is correct
36 Correct 276 ms 23544 KB Output is correct
37 Correct 249 ms 22484 KB Output is correct
38 Correct 164 ms 22520 KB Output is correct
39 Correct 194 ms 22392 KB Output is correct
40 Correct 193 ms 22392 KB Output is correct
41 Correct 729 ms 22584 KB Output is correct
42 Correct 159 ms 22392 KB Output is correct
43 Execution timed out 1573 ms 22392 KB Time limit exceeded
44 Halted 0 ms 0 KB -