제출 #418633

#제출 시각아이디문제언어결과실행 시간메모리
418633Chaska말 (IOI15_horses)C++11
20 / 100
784 ms57676 KiB
#include "horses.h" #include <bits/stdc++.h> #define fo(a,b,c) for (int a=b;a<=c;a++) #define F first #define S second using namespace std; const int MAXN = 5e5+5,mod = 1e9+7; typedef long long ll; typedef pair<ll,ll> i2; int n,x[MAXN],y[MAXN]; ll stX[4*MAXN],r; i2 stY[4*MAXN]; set<int> Set; ll ry; i2 unu; void iniX(int no,int in,int fin) { if (in == fin) { stX[no] = x[in]; return; } int mid=(in+fin)/2; iniX(no*2+1,in,mid); iniX(no*2+2,mid+1,fin); stX[no] = stX[no*2+1]*stX[no*2+2]; stX[no]%= mod; return; } void iniY(int no,int in,int fin) { if (in == fin ) { stY[no].F = y[in]; stY[no].S = in; return; } int mid=(in+fin)/2; iniY(no*2+1,in,mid); iniY(no*2+2,mid+1,fin); stY[no] = max(stY[no*2+1],stY[no*2+2]); return; } void getX(int no,int in,int fin,int u,int v) { if (fin < u || in > v) return; if (u<=in && fin <= v){ r *= stX[no]; r %= mod; return; } int mid=(in+fin)/2; getX(no*2+1,in,mid,u,v); getX(no*2+2,mid+1,fin,u,v); return; } void getY(int no,int in,int fin,int u,int v) { if (fin < u || in > v) return; if (u<=in && fin <= v){ unu = max(unu,stY[no]); return; } int mid=(in+fin)/2; getY(no*2+1,in,mid,u,v); getY(no*2+2,mid+1,fin,u,v); return; } void updX(int no,int in,int fin,int u,int v) { if (fin < u || in > u) return; if (u<=in && fin <= u){ stX[no] = v; return; } int mid=(in+fin)/2; updX(no*2+1,in,mid,u,v); updX(no*2+2,mid+1,fin,u,v); stX[no] = stX[no*2+1]*stX[no*2+2]; stX[no]%= mod; return; } void updY(int no,int in,int fin,int u,int v) { if (fin < u || in > u) return; if (u<=in && fin <= u){ stY[no].F = v; return; } int mid=(in+fin)/2; updY(no*2+1,in,mid,u,v); updY(no*2+2,mid+1,fin,u,v); stY[no] = max(stY[no*2+1],stY[no*2+2]); return; } int sol() { ll k = 0; /// respuesta optima, empezando en pos = -1 ll res = -1; // indice res optima ll q=1; // caballos set<int>::iterator it = Set.end(); it--; vector<int> posres; int tp = 0; while (true) { if (tp > 35) { break; } else { posres.push_back(*it); tp++; //cout << *it << " "; if (it == Set.begin()) { break ;} it--; } } reverse(posres.begin(),posres.end()); posres.push_back(n); if (posres.size()==1) { unu.F=0; unu.S = -1; getY(0,0,n-1,0,n-1); return unu.F; } else { // for (int u : posres) cout << u <<" " ; for (int j=0;j<(int)posres.size()-1;j++) { int i = posres[j]; ll ok = x[i]; ll owo = posres[j+1]-1; unu.F = 0; unu.S = -1; getY(0,0,n-1,i,owo); //cout << unu << " " ; q *= ok; if (k<=q) { res = unu.S; k = unu.F; q = 1; } else { q *= unu.F; if (k<=q) { res = unu.S; k = unu.F; q = 1; } else { q /= unu.F; } } } r=1; getX(0,0,n-1,0,res); r %= mod; r *= y[res]; r %= mod; return r; } } int init(int N, int X[], int Y[]) { n = N; fo(i,0,n-1) x[i] = X[i]; fo(i,0,n-1) y[i] = Y[i]; fo(i,0,n-1) if (x[i] != 1) Set.insert(i); iniX(0,0,n-1); iniY(0,0,n-1); return sol(); } int updateX(int pos, int val) { if (x[pos] == 1 && val > 1) Set.insert(pos); else { if (x[pos] > 1 && val == 1) { Set.erase(pos); } } x[pos] = val; updX(0,0,n-1,pos,val); return sol(); } int updateY(int pos, int val) { y[pos] = val; updY(0,0,n-1,pos,val); return sol(); }

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

horses.cpp: In function 'int sol()':
horses.cpp:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define F first
      |           ^
horses.cpp:126:14: note: in expansion of macro 'F'
  126 |   return unu.F;
      |              ^
horses.cpp:136:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |   getY(0,0,n-1,i,owo);
      |                  ^~~
horses.cpp:157:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  157 |  getX(0,0,n-1,0,res);
      |                 ^~~
horses.cpp:161:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  161 |  return r;
      |         ^
#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...