oj.uz

Submission #31204

# Submission time Handle Problem Language Result Execution time Memory
31204 2017-08-13T14:07:17 Z cscandkswon Horses (IOI15_horses) C++14
17 / 100
 896 ms 41156 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=500005;
const long long MOD=(1e9)+7;

int T[MAXN*3], M[MAXN*3], N, *X, *Y;
set<int, greater<int> > S;

void initTree(int idx, int l, int r){
    if(l==r){
        T[idx]=Y[l];
        return;
    }
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    initTree(lidx, l, m);
    initTree(ridx, m+1, r);
    T[idx]=max(T[lidx], T[ridx]);
}

void updateTree(int idx, int l, int r, int t){
    if(l==r){
        T[idx]=Y[t];
        return;
    }
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    if(t<=m) updateTree(lidx, l, m, t);
    if(t>m) updateTree(ridx, m+1, r, t);
    T[idx]=max(T[lidx], T[ridx]);
}

int queryTree(int idx, int l, int r, int s, int e){
    if(r<s || l>e) return 0;
    if(s<=l && r<=e) return T[idx];
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    return max(queryTree(lidx, l, m, s, e), queryTree(ridx, m+1, r, s, e));
}

void initmultiply(int idx, int l, int r){
    if(l==r){
        M[idx]=X[l];
        return;
    }
    int lidx=idx<<1, ridx=lidx+1, m=(l+r)>>1;
    initmultiply(lidx, l, m);
    initmultiply(ridx, m+1, r);
    M[idx]=(long long)M[lidx]*M[ridx]%MOD;
}

void updatemultiply(int idx, int l, int r, int t){
    if(l==r){
        M[idx]=X[t];
        return;
    }
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    if(t<=m) updatemultiply(lidx, l, m, t);
    if(t>m) updatemultiply(ridx, m+1, r, t);
    M[idx]=(long long)M[lidx]*M[ridx]%MOD;
}

int getmultiply(int idx, int l, int r, int s, int e){
    if(r<s|| l>e) return 1;
    if(s<=l && r<=e) return M[idx];
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    return (long long)getmultiply(lidx, l, m, s, e)*getmultiply(ridx, m+1, r, s, e)%MOD;
}

int getans(){
    long long x=1, y, ans=0, ansy;
    set<int, greater<int> >::iterator pos, nxt, idx;
    for(pos=S.begin(); pos!=S.end(); ++pos){
        x=x*X[*pos];
        if(x>1e9) break;
    }
    x=1;
    if(pos==S.end()) --pos;
    if(pos!=S.begin()){
        nxt=pos; --nxt;
        for(; pos!=S.begin(); pos=nxt, --nxt){
            x=x*X[*pos];
            if(x*(y=queryTree(1, 0, N-1, *pos, (*nxt)-1))>ans){
                ans=x*y;
                ansy=y;
                idx=pos;
            }
        }
    }
    pos=S.begin();
    x=x*X[*pos];
    if(x*(y=queryTree(1, 0, N-1, *pos, N-1))>ans){
        ans=x*y;
        ansy=y;
        idx=pos;
    }
    return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
}

int init(int _N, int _X[], int _Y[]) {
    int i;
    N=_N, X=_X, Y=_Y;
    initTree(1, 0, N-1);
    initmultiply(1, 0, N-1);
    for(i=0; i<N; i++) if(X[i]>1) S.insert(i);
    S.insert(0);
    return getans();
}

int updateX(int pos, int val) {
    if(X[pos]>1 && val==1 && pos)
        S.erase(pos);
    else if(X[pos]==1 && val>1)
        S.insert(pos);
    X[pos]=val;
    updatemultiply(1, 0, N-1, pos);
    return getans();
}

int updateY(int pos, int val) {
    Y[pos]=val;
    updateTree(1, 0, N-1, pos);
    return getans();
}

Compilation message

horses.cpp: In function 'void initmultiply(int, int, int)':
horses.cpp:47:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     M[idx]=(long long)M[lidx]*M[ridx]%MOD;
           ^
horses.cpp: In function 'void updatemultiply(int, int, int, int)':
horses.cpp:58:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     M[idx]=(long long)M[lidx]*M[ridx]%MOD;
           ^
horses.cpp: In function 'int getmultiply(int, int, int, int, int)':
horses.cpp:65:85: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (long long)getmultiply(lidx, l, m, s, e)*getmultiply(ridx, m+1, r, s, e)%MOD;
                                                                                     ^
horses.cpp: In function 'int getans()':
horses.cpp:95:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
                                                 ^
horses.cpp:95:43: warning: 'ansy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
                                           ^

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13748 KB Output is correct
2 Correct 0 ms 13748 KB Output is correct
3 Correct 0 ms 13748 KB Output is correct
4 Correct 0 ms 13748 KB Output is correct
5 Correct 0 ms 13748 KB Output is correct
6 Correct 0 ms 13748 KB Output is correct
7 Correct 0 ms 13748 KB Output is correct
8 Correct 0 ms 13748 KB Output is correct
9 Correct 0 ms 13748 KB Output is correct
10 Correct 0 ms 13748 KB Output is correct
11 Correct 0 ms 13748 KB Output is correct
12 Correct 0 ms 13748 KB Output is correct
13 Correct 0 ms 13748 KB Output is correct
14 Correct 0 ms 13748 KB Output is correct
15 Correct 0 ms 13748 KB Output is correct
16 Correct 0 ms 13748 KB Output is correct
17 Correct 0 ms 13748 KB Output is correct
18 Correct 0 ms 13748 KB Output is correct
19 Correct 0 ms 13748 KB Output is correct
20 Correct 0 ms 13748 KB Output is correct
21 Correct 0 ms 13748 KB Output is correct
22 Correct 0 ms 13748 KB Output is correct
23 Incorrect 0 ms 13748 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 41156 KB Output is correct
2 Incorrect 413 ms 41156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13748 KB Output is correct
2 Correct 0 ms 13748 KB Output is correct
3 Correct 0 ms 13748 KB Output is correct
4 Correct 0 ms 13748 KB Output is correct
5 Correct 0 ms 13748 KB Output is correct
6 Correct 0 ms 13748 KB Output is correct
7 Correct 0 ms 13748 KB Output is correct
8 Correct 0 ms 13748 KB Output is correct
9 Correct 0 ms 13748 KB Output is correct
10 Correct 0 ms 13748 KB Output is correct
11 Correct 0 ms 13748 KB Output is correct
12 Correct 0 ms 13748 KB Output is correct
13 Correct 0 ms 13748 KB Output is correct
14 Correct 0 ms 13748 KB Output is correct
15 Correct 0 ms 13748 KB Output is correct
16 Correct 0 ms 13748 KB Output is correct
17 Correct 0 ms 13748 KB Output is correct
18 Correct 0 ms 13748 KB Output is correct
19 Correct 0 ms 13748 KB Output is correct
20 Correct 0 ms 13748 KB Output is correct
21 Correct 0 ms 13748 KB Output is correct
22 Correct 0 ms 13748 KB Output is correct
23 Incorrect 0 ms 13748 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13748 KB Output is correct
2 Correct 0 ms 13748 KB Output is correct
3 Correct 0 ms 13748 KB Output is correct
4 Correct 0 ms 13748 KB Output is correct
5 Correct 0 ms 13748 KB Output is correct
6 Correct 0 ms 13748 KB Output is correct
7 Correct 0 ms 13748 KB Output is correct
8 Correct 0 ms 13748 KB Output is correct
9 Correct 0 ms 13748 KB Output is correct
10 Correct 0 ms 13748 KB Output is correct
11 Correct 0 ms 13748 KB Output is correct
12 Correct 0 ms 13748 KB Output is correct
13 Correct 0 ms 13748 KB Output is correct
14 Correct 0 ms 13748 KB Output is correct
15 Correct 0 ms 13748 KB Output is correct
16 Correct 0 ms 13748 KB Output is correct
17 Correct 0 ms 13748 KB Output is correct
18 Correct 0 ms 13748 KB Output is correct
19 Correct 0 ms 13748 KB Output is correct
20 Correct 0 ms 13748 KB Output is correct
21 Correct 0 ms 13748 KB Output is correct
22 Correct 0 ms 13748 KB Output is correct
23 Incorrect 0 ms 13748 KB Output isn't correct
24 Halted 0 ms 0 KB -