제출 #837280

#제출 시각아이디문제언어결과실행 시간메모리
837280oscar1f말 (IOI15_horses)C++17
17 / 100
14 ms11604 KiB
#include<bits/stdc++.h> #include "horses.h" using namespace std; using ll=long long; const ll MAX_VAL=100*1000+5,DECA=(1<<17),MODU=1000*1000*1000+7; ll nbVal; int rep; ll multi[MAX_VAL],benef[DECA]; ll arbreMax[2*DECA],arbreProd[2*DECA]; set<ll> listeInter; ll calcMax(ll deb,ll fin) { if (deb==fin) { return arbreMax[deb]; } if (deb%2==1) { return max(arbreMax[deb],calcMax(deb+1,fin)); } if (fin%2==0) { return max(arbreMax[fin],calcMax(deb,fin-1)); } return calcMax(deb/2,fin/2); } ll calcProd(ll deb,ll fin) { if (deb==fin) { return arbreProd[deb]; } if (deb%2==1) { return (arbreProd[deb]*calcProd(deb+1,fin))%MODU; } if (fin%2==0) { return (arbreProd[fin]*calcProd(deb,fin-1))%MODU; } return calcProd(deb/2,fin/2); } void majMax(ll pos,ll val) { benef[pos]=val; pos+=DECA; arbreMax[pos]=val; while (pos>1) { pos/=2; arbreMax[pos]=max(arbreMax[2*pos],arbreMax[2*pos+1]); } } void majProd(ll pos,ll val) { multi[pos]=val; pos+=DECA; arbreProd[pos]=val; while (pos>1) { pos/=2; arbreProd[pos]=(arbreProd[2*pos]*arbreProd[2*pos+1])%MODU; } } void calc() { auto it=listeInter.end(); it--; ll prodCour=1,meilleur=0; while ((*it)!=-1 and prodCour*multi[(*it)]<MODU) { prodCour*=multi[(*it)]; meilleur=max(meilleur,calcMax(DECA+(*it),DECA+nbVal-1)); meilleur*=multi[(*it)]; it--; } if ((*it)==-1) { ll maxi=calcMax(DECA,DECA+nbVal-1); //cout<<meilleur<<" "<<maxi<<endl; if (meilleur>maxi) { rep=meilleur%MODU; } else { rep=maxi; } } else { it++; meilleur%=MODU; if ((*it)>0) { meilleur*=calcProd(DECA,DECA+(*it)-1); } rep=meilleur%MODU; } //cout<<rep<<endl; } int init(int N, int X[], int Y[]) { nbVal=N; for (ll i=0;i<nbVal;i++) { multi[i]=X[i]; benef[i]=Y[i]; } for (ll i=0;i<2*DECA;i++) { arbreProd[i]=1; } for (ll i=0;i<nbVal;i++) { arbreProd[DECA+i]=multi[i]; arbreMax[DECA+i]=benef[i]; } for (ll i=DECA-1;i>0;i--) { arbreProd[i]=(arbreProd[2*i]*arbreProd[2*i+1])%MODU; arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]); } for (ll i=0;i<nbVal;i++) { if (multi[i]>1) { listeInter.insert(i); } } listeInter.insert(-1); //cout<<calc()<<endl; calc(); return rep; } int updateX(int pos, int val) { if (multi[pos]>1) { listeInter.erase(pos); } majProd(pos,val); if (multi[pos]>1) { listeInter.insert(pos); } calc(); return rep; } int updateY(int pos, int val) { majMax(pos,val); calc(); return rep; }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'void calc()':
horses.cpp:74:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |    rep=meilleur%MODU;
      |        ~~~~~~~~^~~~~
horses.cpp:77:8: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   77 |    rep=maxi;
      |        ^~~~
horses.cpp:86:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   86 |   rep=meilleur%MODU;
      |       ~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...