oj.uz

Submission #68614

# Submission time Handle Problem Language Result Execution time Memory
68614 2018-08-17T14:26:10 Z MANcity Horses (IOI15_horses) C++14
34 / 100
 29 ms 10268 KB 
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "horses.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n;
LL X[100002];
LL Y[100002];
struct vert
{
    double gum;
    double ans;
    int pos;
}t[4*100002];
void combine(int v)
{
    if(t[2*v].ans>=(t[2*v].gum+t[2*v+1].ans))
    {
        t[v].ans=t[2*v].ans;
        t[v].pos=t[2*v].pos;
    }
    else
    {
        t[v].ans=(t[2*v].gum+t[2*v+1].ans);
        t[v].pos=t[2*v+1].pos;
    }
    t[v].gum=(t[2*v].gum+t[2*v+1].gum);
}
void build(int left,int right,int v)
{
    if(left==right)
    {
        t[v].gum=(double)log(X[left]);
        t[v].ans=(double)log(X[left])+(double)log(Y[left]);
        t[v].pos=left;
    }
    else
    {
        int m=(left+right)/2;
        build(left,m,2*v);
        build(m+1,right,2*v+1);
        combine(v);
    }
}
void update(int left,int right,int pos,int v)
{
    if(left==right)
    {
        t[v].gum=(double)log(X[left]);
        t[v].ans=(double)log(X[left])+(double)log(Y[left]);
        t[v].pos=left;
    }
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update(left,m,pos,2*v);
        else
            update(m+1,right,pos,2*v+1);
        combine(v);
    }
}
LL mult[4*100002];
void build2(int left,int right,int v)
{
    if(left==right)
        mult[v]=X[left];
    else
    {
        int m=(left+right)/2;
        build2(left,m,2*v);
        build2(m+1,right,2*v+1);
        mult[v]=((LL)mult[2*v]*(LL)mult[2*v+1])%Mod;
    }
}
LL get2(int left,int right,int l,int r,int v)
{
    if(l>r)
        return 1;
    if(left==l && right==r)
        return mult[v];
    int m=(left+right)/2;
    LL A=get2(left,m,l,min(r,m),2*v);
    LL B=get2(m+1,right,max(l,m+1),r,2*v+1);
    return ((LL)A*(LL)B)%Mod;
}
void update2(int left,int right,int pos,int v)
{
    if(left==right)
    {
        mult[v]=X[left];
    }
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update2(left,m,pos,2*v);
        else
            update2(m+1,right,pos,2*v+1);
        mult[v]=((LL)mult[2*v]*(LL)mult[2*v+1])%Mod;
    }
}
int init(int n_0, int x_0[], int y_0[]) {
    n=n_0;
    for1(i,n)
        X[i]=x_0[i-1];
    for1(i,n)
        Y[i]=y_0[i-1];
    build(1,n,1);
    build2(1,n,1);
    return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}

int updateX(int pos, int val) {
    X[pos+1]=val;
    update(1,n,pos+1,1);
    update2(1,n,pos+1,1);
    return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}

int updateY(int pos, int val) {
    Y[pos+1]=val;
    update(1,n,pos+1,1);
    return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:129:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:136:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:142:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 10172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10172 KB Output is correct
2 Correct 2 ms 10172 KB Output is correct
3 Correct 3 ms 10172 KB Output is correct
4 Correct 2 ms 10172 KB Output is correct
5 Correct 2 ms 10172 KB Output is correct
6 Correct 2 ms 10172 KB Output is correct
7 Correct 3 ms 10172 KB Output is correct
8 Correct 2 ms 10172 KB Output is correct
9 Correct 2 ms 10172 KB Output is correct
10 Correct 2 ms 10172 KB Output is correct
11 Correct 3 ms 10172 KB Output is correct
12 Correct 2 ms 10172 KB Output is correct
13 Correct 3 ms 10172 KB Output is correct
14 Correct 2 ms 10172 KB Output is correct
15 Correct 2 ms 10172 KB Output is correct
16 Correct 2 ms 10172 KB Output is correct
17 Correct 2 ms 10172 KB Output is correct
18 Correct 3 ms 10172 KB Output is correct
19 Correct 2 ms 10172 KB Output is correct
20 Correct 2 ms 10172 KB Output is correct
21 Correct 2 ms 10172 KB Output is correct
22 Correct 2 ms 10172 KB Output is correct
23 Correct 3 ms 10172 KB Output is correct
24 Correct 3 ms 10172 KB Output is correct
25 Correct 3 ms 10172 KB Output is correct
26 Correct 3 ms 10172 KB Output is correct
27 Correct 3 ms 10172 KB Output is correct
28 Correct 3 ms 10172 KB Output is correct
29 Correct 3 ms 10172 KB Output is correct
30 Correct 3 ms 10172 KB Output is correct
31 Correct 3 ms 10172 KB Output is correct
32 Correct 3 ms 10172 KB Output is correct
33 Runtime error 29 ms 10220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10220 KB Output is correct
2 Correct 2 ms 10220 KB Output is correct
3 Correct 2 ms 10220 KB Output is correct
4 Correct 3 ms 10220 KB Output is correct
5 Correct 2 ms 10220 KB Output is correct
6 Correct 2 ms 10220 KB Output is correct
7 Correct 2 ms 10220 KB Output is correct
8 Correct 2 ms 10220 KB Output is correct
9 Correct 2 ms 10220 KB Output is correct
10 Correct 2 ms 10220 KB Output is correct
11 Correct 2 ms 10220 KB Output is correct
12 Correct 2 ms 10220 KB Output is correct
13 Correct 3 ms 10220 KB Output is correct
14 Correct 3 ms 10220 KB Output is correct
15 Correct 2 ms 10220 KB Output is correct
16 Correct 2 ms 10220 KB Output is correct
17 Correct 2 ms 10220 KB Output is correct
18 Correct 2 ms 10220 KB Output is correct
19 Correct 2 ms 10220 KB Output is correct
20 Correct 3 ms 10220 KB Output is correct
21 Correct 2 ms 10220 KB Output is correct
22 Correct 2 ms 10220 KB Output is correct
23 Correct 4 ms 10220 KB Output is correct
24 Correct 3 ms 10220 KB Output is correct
25 Correct 3 ms 10220 KB Output is correct
26 Correct 2 ms 10220 KB Output is correct
27 Correct 3 ms 10220 KB Output is correct
28 Correct 4 ms 10220 KB Output is correct
29 Correct 3 ms 10220 KB Output is correct
30 Correct 3 ms 10220 KB Output is correct
31 Correct 3 ms 10220 KB Output is correct
32 Correct 3 ms 10220 KB Output is correct
33 Runtime error 21 ms 10268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -