제출 #524133

#제출 시각아이디문제언어결과실행 시간메모리
524133Lobo말 (IOI15_horses)C++17
100 / 100
1438 ms73240 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define maxn 550000 int n, a[maxn], b[maxn], trmx[4*maxn], trp[4*maxn]; map<int,pair<int,int>> lr; int mod = 1e9 + 7; dbl logmax, logtot; void attmx(int no, int l, int r, int pos, int val) { if(l > pos || r < pos) return; else if(l == r) trmx[no] = val; else { int f1 = 2*no; int f2 = 2*no + 1; int mid = (l+r)>>1; attmx(f1,l,mid,pos,val); attmx(f2,mid+1,r,pos,val); trmx[no] = max(trmx[f1],trmx[f2]); } } int qrmx(int no, int l, int r, int L, int R) { if(l > R || r < L) return 0; else if(l >= L && r <= R) return trmx[no]; else { int f1 = 2*no; int f2 = 2*no + 1; int mid = (l+r)>>1; return max(qrmx(f1,l,mid,L,R),qrmx(f2,mid+1,r,L,R)); } } void attp(int no, int l, int r, int pos, int val) { if(l > pos || r < pos) return; else if(l == r) trp[no] = val; else { int f1 = 2*no; int f2 = 2*no + 1; int mid = (l+r)>>1; attp(f1,l,mid,pos,val); attp(f2,mid+1,r,pos,val); trp[no] = (trp[f1]*trp[f2])%mod; } } int qrp(int no, int l, int r, int L, int R) { if(l > R || r < L) return 1; else if(l >= L && r <= R) return trp[no]; else { int f1 = 2*no; int f2 = 2*no + 1; int mid = (l+r)>>1; return (qrp(f1,l,mid,L,R)*qrp(f2,mid+1,r,L,R))%mod; } } int qrr() { auto it = lr.end(); it--; dbl logcur = logtot; int ans = 0; dbl anslg = -inf; while(true) { int l = it->fr; int r = it->sc.fr; int p = it->sc.sc; int mx = qrmx(1,0,n-1,l,r); dbl anscur = log2(mx) + logcur; if(anscur >= anslg) { anslg = anscur; ans = (qrp(1,0,n-1,0,r)*mx)%mod; } logcur -= log2(p); if(logcur + logmax < logtot || it == lr.begin()) break; it--; } return ans; } int32_t init(int32_t N, int32_t X[], int32_t Y[]) { n = N; logtot = 0; logmax = 31; for(int i = 0; i < n; i++) { a[i] = X[i]; logtot+= log2(a[i]); attp(1,0,n-1,i,a[i]); } for(int i = 0; i < n; i++) { b[i] = Y[i]; attmx(1,0,n-1,i,b[i]); } for(int i = 0; i < n;) { if(a[i] != 1) { lr[i] = mp(i,a[i]); i++; } else { int ant = i; while(i < n && a[i] == 1) { i++; } lr[ant] = mp(i-1,1); } } return qrr(); } int32_t updateX(int32_t pos, int32_t val) { if(val == a[pos]) { return qrr(); } attp(1,0,n-1,pos,val); logtot-= log2(a[pos]); logtot+= log2(val); if(a[pos] != 1 && val != 1) { a[pos] = val; lr[pos] = mp(pos,val); return qrr(); } auto it = lr.upper_bound(pos); it--; if(val == 1) { //quero pegar o cara da direita e da esquerda e juntar com esse vector<int> tir; int l = pos; int r = pos; if(it != lr.begin()) { it--; //tiro ele se for igual a 1 if(it->sc.sc == 1) { l = it->fr; tir.pb(it->fr); } it++; } it++; if(it != lr.end()) { if(it->sc.sc == 1) { r = it->sc.fr; tir.pb(it->fr); } } it--; tir.pb(it->fr); for(auto x : tir) { lr.erase(x); } lr[l] = mp(r,1); } else { //quero pegar o cara da direita e da esquerda e separar int l = it->fr; int r = it->sc.fr; lr.erase(l); if(l != pos) { //inserir (l,pos-1) lr[l] = mp(pos-1,1); } lr[pos] = mp(pos,val); if(r != pos) { lr[pos+1] = mp(r,1); } } a[pos] = val; return qrr(); } int32_t updateY(int32_t pos, int32_t val) { b[pos] = val; attmx(1,0,n-1,pos,val); return qrr(); }

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

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:130:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  130 |     return qrr();
      |            ~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:135:19: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  135 |         return qrr();
      |                ~~~^~
horses.cpp:145:19: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  145 |         return qrr();
      |                ~~~^~
horses.cpp:198:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  198 |     return qrr();
      |            ~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:205:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  205 |     return qrr();
      |            ~~~^~
#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...