oj.uz

Submission #86802

# Submission time Handle Problem Language Result Execution time Memory
86802 2018-11-27T15:11:11 Z JustasZ Horses (IOI15_horses) C++14
0 / 100
 824 ms 49244 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) "["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=5e5+100;
const int mod=1e9+7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll pwr(ll a, ll pw)
{
    ll ret=1;
    while(pw>0)
    {
        if(pw&1)ret=(ret*a)%mod;
        a=(a*a)%mod;
        pw>>=1;
    }
    return ret;
}
ll modinv(ll a)
{
    return pwr(a, mod-2);
}
int N;
ll X[maxn], Y[maxn], seg[maxn*8];
set<int>pos;
void build(int id=1, int l=0, int r=N-1)
{
    if(l == r)
    {
        seg[id]=Y[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    seg[id]=max(seg[id*2], seg[id*2+1]);
}
void modify(int p, ll d, int id=1, int l=0, int r=N-1)
{
    if(l == r)
    {
        seg[id]+=d;
        return;
    }
    int mid=(l+r)/2;
    if(p <= mid)modify(p, d, id*2, l, mid);
    else modify(p, d, id*2+1, mid+1, r);
    seg[id]=max(seg[id*2], seg[id*2+1]);
}
ll query(int x, int y, int id=1, int l=0, int r=N-1)
{
    if(l > y || r < x)return 0;
    if(l >= x && r <= y)return seg[id];
    int mid=(l+r)/2;
    return max(query(x, y, id*2, l, mid), query(x, y, id*2+1, mid+1, r));
}
struct BIT
{
    ll F[maxn];
    void upd(int p, ll val)
    {
        for(; p<=N; p+=p&-p)
        {
            F[p]=(F[p]*val)%mod;
        }
    }
    ll get(int p)
    {
        ll ret=1;
        for(; p>0; p-=p&-p)
            ret=(ret*F[p])%mod;
        return ret;
    }
}tree;
int getans()
{
    auto it=prev(pos.end());
    ll ret=query(0, N-1);
    for(int c=0; c<=30; c++)
    {
        ret=max(ret, (tree.get(*it+1)*query(*it, N-1))%mod);
        if(it == pos.begin())break;
        --it;
    }
    return (int)ret;
}
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];
    for(int i=N-1; i>=0; i--)
        if(X[i] >= 2)
            pos.insert(i);
    build();
    for(int i=1; i<=N; i++)
        tree.F[i]=1;
    for(int i=0; i<N; i++)
        tree.upd(i+1, X[i]);
    return getans();
}
int updateX(int p, int val)
{
    tree.upd(p+1, modinv(X[p]));
    if(X[p] >= 2)pos.erase(p);
    X[p]=val;
    if(X[p] >= 2)pos.insert(p);
    tree.upd(p+1, val);
    return getans();
}
int updateY(int p, int val)
{
    ll d=val-Y[p];
    modify(p, d);
    Y[p]=val;
    return getans();
}
/*int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int A[]={2, 1, 3};
    int B[]={3, 4, 1};
    cout<<init(3, A, B)<<"\n";
    cout<<updateY(1, 2)<<"\n";
    return 0;
}*/

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Runtime error 6 ms 740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Runtime error 4 ms 812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 824 ms 49244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49244 KB Output is correct
2 Correct 2 ms 49244 KB Output is correct
3 Correct 2 ms 49244 KB Output is correct
4 Correct 2 ms 49244 KB Output is correct
5 Runtime error 4 ms 49244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49244 KB Output is correct
2 Correct 2 ms 49244 KB Output is correct
3 Correct 2 ms 49244 KB Output is correct
4 Correct 2 ms 49244 KB Output is correct
5 Runtime error 4 ms 49244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -