제출 #274172

#제출 시각아이디문제언어결과실행 시간메모리
274172A02말 (IOI15_horses)C++14
17 / 100
1192 ms61392 KiB
#include "horses.h" #include <vector> #include <algorithm> #include <set> #include <utility> #include <iostream> #include <math.h> using namespace std; long long prime = 1000000007; long long mod_exp(long long a, long long k){ if (k == 0){ return 1; } if (k == 1){ return a; } long long a1 = mod_exp(a, k / 2); if (k % 2 == 1){ return (((a1 * a1) % prime) * a) % prime; } return (a1 * a1) % prime; } void updateModSegTree(vector<long long> &tree, int p, long long t){ int N = tree.size() / 2; tree[p + N] = (tree[p + N] * t) % prime; for (p = (p + N) / 2; p > 0; p = p / 2){ tree[p] = (tree[2 * p] * tree[2 * p + 1]) % prime; } } long long queryModSegTree(vector<long long> &tree, int l, int r){ int N = tree.size() / 2; long long total = 1; for (l += N, r += N; l < r; l /= 2, r /= 2){ if (l % 2 == 1){ total = (total * tree[l++]) % prime; } if (r % 2 == 1){ total = (total * tree[--r]) % prime; } } return total; } void apply(vector<long double> &tree, vector<long double> &delayed, int p, long double t){ tree[p] += t; if (p < delayed.size()){ delayed[p] += t; } } void build(vector<long double> &tree, vector<long double> &delayed, int p, vector<int> &answer_node){ while (p > 1){ p /= 2; answer_node[p] = answer_node[2 * p + 1]; if (tree[2 * p] > tree[2 * p + 1]){ answer_node[p] = answer_node[2 * p]; } tree[p] = max(tree[2 * p], tree[2 * p + 1]) + delayed[p]; } } void push(vector<long double> &tree, vector<long double> &delayed, int p){ int N = tree.size() / 2; int h = sizeof(int) * 8 - __builtin_clz(N); for (int s = h; s > 0; s--){ int i = p >> s; if (delayed[i] != 0){ apply(tree, delayed, 2 * i, delayed[i]); apply(tree, delayed, 2 * i + 1, delayed[i]); delayed[i] = 0; } } } void updateMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, long double t, vector<int> &answer_node){ int n = tree.size() / 2; l += n; r += n; int L = l; int R = r; for (; l < r; l/=2, r/=2){ if (l % 2 == 1){ apply(tree, delayed, l++, t); } if (r % 2 == 1){ apply(tree, delayed, --r, t); } } build(tree, delayed, L, answer_node); build(tree, delayed, R - 1, answer_node); } int queryMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, vector<int> &answer_node){ int N = tree.size() / 2; l += N; r += N; push(tree, delayed, l); push(tree, delayed, r - 1); long double answer = -1; int answer_n = -1; for (; l < r; l /= 2, r /= 2){ if (l % 2 == 1){ if (tree[l] > answer){ answer_n = answer_node[l]; } answer = max(answer, tree[l++]); } if (r % 2 == 1){ if (tree[r - 1] > answer){ answer_n = answer_node[r - 1]; } answer = max(answer, tree[--r]); } } //cout << answer << endl; return answer_n; } vector<long long> mod_seg_tree; vector<long double> max_seg_tree; vector<long double> max_seg_tree_delayed; vector<int> answer_node; vector<long long> Xi; vector<long long> Yi; int init(int N, int X[], int Y[]) { mod_seg_tree = vector<long long> (2 * N, 1); max_seg_tree = vector<long double> (2 * N, 0.0); max_seg_tree_delayed = vector<long double> (N, 0.0); answer_node = vector<int> (2 * N, 0); for (int i = 0; i < N; i++){ answer_node[i + N] = i; Xi.push_back(X[i]); Yi.push_back(Y[i]); } for (int i = 0; i < N; i++){ //cout << i << ' ' << X[i] << endl; updateModSegTree(mod_seg_tree, i, X[i]); //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl; updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, N, log(X[i]), answer_node); updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, i + 1, log(Y[i]), answer_node); } int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node); //cout << best << endl; long long answer = queryModSegTree(mod_seg_tree, 0, best + 1); //cout << 'a' << endl; //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl; return (answer * Yi[best]) % prime; } int updateX(int pos, int val) { int N = max_seg_tree.size() / 2; updateModSegTree(mod_seg_tree, pos, val * mod_exp(Xi[pos], prime - 1)); updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, N, log(val) - log(Xi[pos]), answer_node); Xi[pos] = val; int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node); //cout << best << endl; long long answer = queryModSegTree(mod_seg_tree, 0, best + 1); //cout << 'a' << endl; //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl; return (answer * Yi[best]) % prime; } int updateY(int pos, int val) { int N = max_seg_tree.size() / 2; updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, pos + 1, log(val) - log(Yi[pos]), answer_node); Yi[pos] = val; int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node); //cout << best << endl; long long answer = queryModSegTree(mod_seg_tree, 0, best + 1); //cout << 'a' << endl; //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl; return (answer * Yi[best]) % prime; }

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

horses.cpp: In function 'void updateModSegTree(std::vector<long long int>&, int, long long int)':
horses.cpp:34:25: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'long long int queryModSegTree(std::vector<long long int>&, int, int)':
horses.cpp:48:25: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   48 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'void apply(std::vector<long double>&, std::vector<long double>&, int, long double)':
horses.cpp:70:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     if (p < delayed.size()){
      |         ~~^~~~~~~~~~~~~~~~
horses.cpp: In function 'void push(std::vector<long double>&, std::vector<long double>&, int)':
horses.cpp:95:25: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   95 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp:97:29: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   97 |     int h = sizeof(int) * 8 - __builtin_clz(N);
      |             ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void updateMaxSegTree(std::vector<long double>&, std::vector<long double>&, int, int, long double, std::vector<int>&)':
horses.cpp:115:25: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |     int n = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'int queryMaxSegTree(std::vector<long double>&, std::vector<long double>&, int, int, std::vector<int>&)':
horses.cpp:141:25: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  141 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:205:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  205 |     return (answer * Yi[best]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:210:30: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  210 |  int N = max_seg_tree.size() / 2;
      |          ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:221:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  221 |     return (answer * Yi[best]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:226:33: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  226 |     int N = max_seg_tree.size() / 2;
      |             ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:236:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  236 |     return (answer * Yi[best]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
#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...