제출 #297470

#제출 시각아이디문제언어결과실행 시간메모리
297470humbertoyusta말 (IOI15_horses)C++14
57 / 100
1558 ms43768 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define maxn 500050 #define mod 1000000007 #define ll long long #define f first #define s second #define ii pair<ll,ll> #define db(x) cerr << #x << ": " << (x) << '\n'; struct node{ ll mx, my, px; } st[maxn*4]; int x[maxn], y[maxn], n; node join(node a,node b){ return { max( a.mx , b.mx ) , max( a.my , b.my ) , a.px * b.px % mod }; } void build(int nod,int l,int r){ if( l == r ){ st[nod] = { x[l] , y[l] , x[l] }; return; } int mi = ( l + r ) >> 1; build(2*nod,l,mi); build(2*nod+1,mi+1,r); st[nod] = join( st[2*nod] , st[2*nod+1] ); } void update(int nod,int l,int r,int id){ if( l == r ){ st[nod] = { x[l] , y[l] , x[l] }; return; } int mi = ( l + r ) >> 1; if( id <= mi ) update(2*nod,l,mi,id); else update(2*nod+1,mi+1,r,id); st[nod] = join( st[2*nod] , st[2*nod+1] ); } int queryx(int nod,int l,int r,int xx,int yy){ if( l > yy || r < xx || l > r ) return 0; if( l == r ){ if( st[nod].mx > 1 ) return l; return 0; } int mi = ( l + r ) >> 1; if( l >= xx && r <= yy ){ if( st[2*nod+1].mx > 1 ) return queryx(2*nod+1,mi+1,r,xx,yy); if( st[2*nod].mx > 1 ) return queryx(2*nod,l,mi,xx,yy); return 0; } return max( queryx(2*nod,l,mi,xx,yy) , queryx(2*nod+1,mi+1,r,xx,yy) ); } node queryy(int nod,int l,int r,int xx,int yy){ if( l > yy || r < xx || l > r ) return { 0 , 0 , 1 }; if( l >= xx && r <= yy ) return st[nod]; int mi = ( l + r ) >> 1; return join( queryy(2*nod,l,mi,xx,yy) , queryy(2*nod+1,mi+1,r,xx,yy) ); } int solve(){ ll res = (ll)x[n] * y[n];//db(res) int id = n; bool moduled = 0; if( res < mod ){ for(int i=1; i<=32; i++){ int nid = queryx(1,1,n,1,id-1); if( nid == 0 ) break; node f = queryy(1,1,n,nid,id-1); res = max( res , f.my ); res *= f.px; id = nid; if( res >= mod ){ moduled = 1; res %= mod; break; } } } else{ res %= mod; moduled = 1; } node cc = queryy(1,1,n,1,id-1); res *= cc.px; if( res >= mod ){ res %= mod; moduled = 1; } if( !moduled ){ res = max( res , cc.my ); } return res; } int init(int N, int X[], int Y[]) { n = N; for(int i=0; i<N; i++){ x[i+1] = X[i]; y[i+1] = Y[i]; } build(1,1,N); return solve(); } int updateX(int pos, int val) { x[pos+1] = val; update(1,1,n,pos+1); return solve(); } int updateY(int pos, int val) { y[pos+1] = val; update(1,1,n,pos+1); return solve(); }

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

horses.cpp: In function 'int solve()':
horses.cpp:115:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |     return res;
      |            ^~~
#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...