Submission #393048

#	Time	Username	Problem	Language	Result	Execution time	Memory
393048		cpp219	Horses (IOI15_horses)	C++14	0 / 100	1484 ms	91860 KiB

horses

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;
ll X[N],Y[N],sz;
struct elem{
    ll mu,nhan,md;
};

void Fix(elem &x){
    x.nhan += x.md/mod; x.md %= mod;
    x.mu += x.nhan/mod; x.nhan %= mod;
}

elem operator * (elem x,ll val){
    elem now = {x.mu,x.nhan,x.md * val};
    Fix(now); return now;
}

elem operator / (elem x,ll val){
    ll cur = x.nhan*mod + x.md;
    elem now = {x.mu,0,cur/val}; Fix(now); return now;
}

elem Maximum(elem x,elem y){
    if (x.mu != y.mu){
        if (x.mu > y.mu) return x;
        return y;
    }
    if (x.nhan != y.nhan){
        if (x.nhan > y.nhan) return x;
        return y;
    }
    if (x.md > y.md) return x; return y;
}

elem st[4*N];
ll lazyC[4*N],lazyN[4*N];

void Pass(ll id){
    ll v1 = lazyN[id],v2 = lazyC[id]; lazyN[id] = 1; lazyC[id] = 1;
    st[id*2] = st[id*2] * v1; st[id*2] = st[id*2] / v2; lazyN[id*2] = v1;  lazyC[id*2] = v2;
    st[id*2 + 1] = st[id*2 + 1] * v1; st[id*2 + 1] = st[id*2 + 1] / v2;
    lazyN[id*2 + 1] = v1; lazyC[id*2 + 1] = v2;
}

/// -val mean /val    val mean *val
void upd(ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        if (val > 0) st[id] = st[id] * abs(val),lazyN[id] = val;
        else st[id] = st[id] / -val,lazyC[id] = -val;
        return;
    }
    ll mid = (l + r)/2; Pass(id);
    upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
    st[id] = Maximum(st[id*2],st[id*2 + 1]);
}

void out(elem x){
    cout<<x.mu<<" "<<x.nhan<<" "<<x.md; exit(0);
}

int updateX(int pos,int val){
    pos++;
    upd(1,1,sz,pos,sz,-X[pos - 1]); upd(1,1,sz,pos,sz,val);
    X[pos - 1] = val;
    return st[1].md;
}

int updateY(int pos,int val){
    pos++;
    upd(1,1,sz,pos,pos,-Y[pos - 1]); upd(1,1,sz,pos,pos,val);
    Y[pos - 1] = val;
    return st[1].md;
}

int init(int n,int P[],int Q[]){
    sz = n;
    for (ll i = 1;i <= 4*n;i++){
        lazyC[i] = lazyN[i] = 1;
        st[i] = {0,0,1};
    }
    for (ll i = 0;i < n;i++){
        X[i] = P[i]; Y[i] = Q[i];
        upd(1,1,n,i + 1,n,P[i]); upd(1,1,n,i + 1,i + 1,Q[i]);
    }
    return st[1].md;
}

Compilation message (stderr)

horses.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
horses.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
horses.cpp: In function 'elem Maximum(elem, elem)':
horses.cpp:43:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   43 |     if (x.md > y.md) return x; return y;
      |     ^~
horses.cpp:43:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   43 |     if (x.md > y.md) return x; return y;
      |                                ^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:77:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |     return st[1].md;
      |            ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:84:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |     return st[1].md;
      |            ~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |     return st[1].md;
      |            ~~~~~~^~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23