Submission #541228

#	Time	Username	Problem	Language	Result	Execution time	Memory
541228		new_acc	Horses (IOI15_horses)	C++14	100 / 100	193 ms	58560 KiB

horses

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const ll mod=1e9+7;
const int SS=1<<19;
struct item{
    ll ilo,ilp,ilk;
    int w;
};
pair<ll,ll>t[N];
item seg[(SS<<1)+10];
item comb(item a,item b){
    item res;
    res.ilo=(a.ilo*b.ilo)%mod;
    if(b.ilp==LLONG_MAX){
        res.ilp=LLONG_MAX;
        res.ilk=b.ilk;
        res.w=b.w;
    }else{
        if(t[a.w].se<a.ilk*b.ilp or t[a.w].se<a.ilk*b.ilp*t[b.w].se){
            res.w=b.w;
            res.ilk=b.ilk;
            if(a.ilp>(ll)1e9 or b.ilp*a.ilk>(ll)1e9) res.ilp=LLONG_MAX;
            else res.ilp=a.ilp*a.ilk*b.ilp;
        }else{
            res.w=a.w;
            res.ilp=a.ilp;
            res.ilk=a.ilk*b.ilp*b.ilk;
        }
    }
    if(res.ilp>(ll)1e9) res.ilp=LLONG_MAX;
    return res;
}
void upd(int ind){
    ind+=SS;
    seg[ind].w=ind-SS,seg[ind].ilo=t[ind-SS].fi;
    seg[ind].ilp=t[ind-SS].fi,seg[ind].ilk=1;
    for(ind>>=1;ind>0;ind>>=1) seg[ind]=comb(seg[ind<<1],seg[(ind<<1)+1]);
}
int Query(int a,int b){
    ll res=1;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) (res*=seg[a+1].ilo)%=mod;
        if(b&1) (res*=seg[b-1].ilo)%=mod;
    }
    return res;
}
int init(int n,int x[],int y[]){
    for(int i=0;i<n;i++) t[i+1]={x[i],y[i]};
    for(int ind=1;ind<=(SS<<1);ind++) seg[ind].ilo=1,seg[ind].ilp=1,seg[ind].ilk=1;
    for(int i=1;i<=n;i++) upd(i);
    return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
}
int updateX(int pos,int val){
    pos++;
    t[pos].fi=val;
    upd(pos);
    return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
}
int updateY(int pos,int val){
    pos++;
    t[pos].se=val;
    upd(pos);
    return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
}

Compilation message (stderr)

horses.cpp: In function 'int Query(int, int)':
horses.cpp:52:12: warning: conversion from 'll' {aka 'long long unsigned int'} to 'int' may change value [-Wconversion]
   52 |     return res;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:58:46: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   58 |     return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:64:46: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   64 |     return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:70:46: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   70 |     return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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