Submission #761902

#	Time	Username	Problem	Language	Result	Execution time	Memory
761902		Ahmed57	Horses (IOI15_horses)	C++17	0 / 100	360 ms	67976 KiB

horses

#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
//Fast
long long fast(long long a,long long b){
    if(b==0)return 1;
    if(b==1)return a%mod;
    long long ha = fast(a,b/2)%mod;
    if(b%2==0)return (ha*ha)%mod;
    else return (((ha*ha)%mod)*a)%mod;
}
long long seg[800001],lazy[800001];
long long seg2[800001],lazy2[800001];
void prop(int p,int l,int r){
    seg[p]*=lazy[p];
    seg[p]%=mod;
    seg2[p]+=lazy2[p];
    if(l!=r){
        lazy[p*2]*=lazy[p];
        lazy[p*2]%=mod;
        lazy2[p*2]+=lazy2[p];
        lazy[p*2+1]*=lazy[p];
        lazy[p*2+1]%=mod;
        lazy2[p*2+1]+=lazy2[p];
    }
    lazy[p] = 1;
    lazy2[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val,long long val2){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]*=val;
        lazy[p]%=mod;
        lazy2[p]+=val2;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val,val2);
    update(p*2+1,md+1,r,lq,rq,val,val2);
    if(seg2[p*2]>seg2[p*2+1]){
        seg2[p]= seg2[p*2];
        seg[p] = seg[p*2];
    }else{
        seg2[p]= seg2[p*2+1];
        seg[p] = seg[p*2+1];
    }
}
pair<long long,long long> query(int p,int l,int r,int lq,int rq){
    prop(p,l,r);
    if(l>=lq&&r<=rq)return {seg[p],seg2[p]};
    if(l>rq||r<lq)return {0,-1};
    int md = (l+r)/2;
    pair<long long,long long> p1 = query(p*2,l,md,lq,rq);
    pair<long long,long long> p2 = query(p*2+1,md+1,r,lq,rq);
    if(p1.second>p2.second)return p1;
    else return p2;
}
int n;
vector<long long> x,y;
long long init(int N,int X[],int Y[]){
    n = N;
    for(int i = 0;i<=8e5;i++){
        seg[i] = 1, lazy[i] = 1;
        seg2[i] = 0 , lazy2[i] = 0;
    }
    for(int i = 0;i<n;i++){
        x.push_back(X[i]);
        y.push_back(Y[i]);
        update(1,1,n,i+1,n,X[i],log2(X[i]));
        update(1,1,n,i+1,i+1,Y[i],log2(Y[i]));
    }
    return query(1,1,n,1,n).first;
}long long updateX(int pos,int val){
     update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log2(x[pos]));
     x[pos] = val;
     update(1,1,n,pos+1,n,x[pos],log2(x[pos]));
     return query(1,1,n,1,n).first;
}long long updateY(int pos,int val){
     update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log2(y[pos]));
     y[pos] = val;
     update(1,1,n,pos+1,pos+1,y[pos],log2(y[pos]));
     return query(1,1,n,1,n).first;
}/*
int main(){
    init(3,{2,1,3},{3,4,1});
    cout<<updateX(0,1)<<endl;
}*/

Compilation message (stderr)

horses.cpp: In function 'long long int init(int, int*, int*)':
horses.cpp:71:37: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   71 |         update(1,1,n,i+1,n,X[i],log2(X[i]));
      |                                 ~~~~^~~~~~
horses.cpp:72:39: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   72 |         update(1,1,n,i+1,i+1,Y[i],log2(Y[i]));
      |                                   ~~~~^~~~~~
horses.cpp: In function 'long long int updateX(int, int)':
horses.cpp:76:46: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   76 |      update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log2(x[pos]));
      |                                              ^~~~~~~~~~~~~
horses.cpp:78:38: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   78 |      update(1,1,n,pos+1,n,x[pos],log2(x[pos]));
      |                                  ~~~~^~~~~~~~
horses.cpp: In function 'long long int updateY(int, int)':
horses.cpp:81:50: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   81 |      update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log2(y[pos]));
      |                                                  ^~~~~~~~~~~~~
horses.cpp:83:42: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   83 |      update(1,1,n,pos+1,pos+1,y[pos],log2(y[pos]));
      |                                      ~~~~^~~~~~~~

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