제출 #778261

#제출 시각아이디문제언어결과실행 시간메모리
778261danikoynov말 (IOI15_horses)C++14
37 / 100
480 ms52940 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e5 + 10; const ll mod = 1e9 + 7; ll x[maxn], y[maxn], n; ll prod_tree[4 * maxn]; void build_prod_tree(int root, int left, int right) { if (left == right) { prod_tree[root] = x[left]; return; } int mid = (left + right) / 2; build_prod_tree(root * 2, left, mid); build_prod_tree(root * 2 + 1, mid + 1, right); prod_tree[root] = (prod_tree[root * 2] * prod_tree[root * 2 + 1]) % mod; } void update_prod(int root, int left, int right, int pos) { if (left == right) { prod_tree[root] = x[left]; return; } int mid = (left + right) / 2; if (pos <= mid) update_prod(root * 2, left, mid, pos); else update_prod(root * 2 + 1, mid + 1, right, pos); prod_tree[root] = (prod_tree[root * 2] * prod_tree[root * 2 + 1]) % mod; } ll prod_query(int root, int left, int right, int qleft, int qright) { if (left > qright || right < qleft) return 1; if (left >= qleft && right <= qright) return prod_tree[root]; int mid = (left + right) / 2; return (prod_query(root * 2, left, mid, qleft, qright) * prod_query(root * 2 + 1, mid + 1, right, qleft, qright)) % mod; } ll breed_tree[4 * maxn]; void build_breed_tree(int root, int left, int right) { if (left == right) { breed_tree[root] = y[left]; return; } int mid = (left + right) / 2; build_breed_tree(root * 2, left, mid); build_breed_tree(root * 2 + 1, mid + 1, right); breed_tree[root] = max(breed_tree[root * 2], breed_tree[root * 2 + 1]); } void update_breed(int root, int left, int right, int pos) { if (left == right) { breed_tree[root] = y[left]; return; } int mid = (left + right) / 2; if (pos <= mid) update_breed(root * 2, left, mid, pos); else update_breed(root * 2 + 1, mid + 1, right, pos); breed_tree[root] = max(breed_tree[root * 2], breed_tree[root * 2 + 1]); } ll breed_query(int root, int left, int right, int qleft, int qright) { if (left > qright || right < qleft) return 0; if (left >= qleft && right <= qright) return breed_tree[root]; int mid = (left + right) / 2; return max(breed_query(root * 2, left, mid, qleft, qright), breed_query(root * 2 + 1, mid + 1, right, qleft, qright)); } set < int > active; ll action() { ll up = y[n - 1], dw = 1, pos = n - 1; ll div = 1; set < int > :: reverse_iterator it; //if (*active.begin() != 0) // active.insert(0); if (active.empty()) { pos = 0; } for (it = active.rbegin(); it != active.rend(); it ++) { ll cur = breed_query(1, 0, n - 1, *it, n - 1); if (div > 1e9) break; ///cout << *it << " " << cur << " " << div << endl; if (cur * dw >= up * div) { up = cur; dw = div; pos = *it; } div = div * x[*it]; } /**for (int i = n - 2; i >= 0; i --) { div = div * x[i + 1]; if (div > 1e9) break; ///cout << i << " : " << y[i] << " " << div << endl; /// y[i] / div >? up / dw if (y[i] * dw >= up * div) { ///cout << " " << up << " : " << dw << endl; up = y[i]; dw = div; pos = i; } }*/ ///cout << pos << endl; ll ans = prod_query(1, 0, n - 1, 0, pos); //for (int i = 0; i <= pos; i ++) // ans = (ans * x[i]) % mod; ans = (ans * breed_query(1, 0, n - 1, pos, n - 1)) % mod; return ans; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i ++) { if (X[i] > 1) active.insert(i); x[i] = X[i]; y[i] = Y[i]; } build_prod_tree(1, 0, n - 1); build_breed_tree(1, 0, n - 1); return action(); } int updateX(int pos, int val) { if (x[pos] > 1 && pos != 0) active.erase(pos); x[pos] = val; if (x[pos] > 1 && pos != 0) active.insert(pos); update_prod(1, 0, n - 1, pos); return action(); } int updateY(int pos, int val) { y[pos] = val; update_breed(1, 0, n - 1, pos); return action(); }

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

horses.cpp: In function 'll action()':
horses.cpp:120:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |         ll cur = breed_query(1, 0, n - 1, *it, n - 1);
      |                                    ~~^~~
horses.cpp:120:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |         ll cur = breed_query(1, 0, n - 1, *it, n - 1);
      |                                                ~~^~~
horses.cpp:121:13: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  121 |         if (div > 1e9)
      |             ^~~
horses.cpp:151:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |     ll ans = prod_query(1, 0, n - 1, 0, pos);
      |                               ~~^~~
horses.cpp:151:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |     ll ans = prod_query(1, 0, n - 1, 0, pos);
      |                                         ^~~
horses.cpp:154:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  154 |     ans = (ans * breed_query(1, 0, n - 1, pos, n - 1)) % mod;
      |                                    ~~^~~
horses.cpp:154:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  154 |     ans = (ans * breed_query(1, 0, n - 1, pos, n - 1)) % mod;
      |                                           ^~~
horses.cpp:154:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  154 |     ans = (ans * breed_query(1, 0, n - 1, pos, n - 1)) % mod;
      |                                                ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:167:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  167 |     build_prod_tree(1, 0, n - 1);
      |                           ~~^~~
horses.cpp:168:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  168 |     build_breed_tree(1, 0, n - 1);
      |                            ~~^~~
horses.cpp:169:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  169 |     return action();
      |            ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:179:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  179 |     update_prod(1, 0, n - 1, pos);
      |                       ~~^~~
horses.cpp:180:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  180 |     return action();
      |            ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:186:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  186 |     update_breed(1, 0, n - 1, pos);
      |                        ~~^~~
horses.cpp:187:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  187 |     return action();
      |            ~~~~~~^~
#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...