이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int p = 1e9 + 7;
typedef pair<int,int> P;
struct SegTree {
vector<int> seg1, seg2, seg3;
int MAX;
void init(int N) {
int i;
for(i=2;i<2*N;i*=2) {}
MAX = i;
seg1.resize(i);
seg2.resize(i);
seg3.resize(i);
}
void cons() {
for(int i=MAX/2-1;i>=1;i--) {
seg1[i] = max(seg1[2*i],seg1[2*i+1]);
seg2[i] = max(seg2[2*i],seg2[2*i+1]);
seg3[i] = 1LL * seg3[2*i] * seg3[2*i+1] % p;
}
}
void update(int n) {
n += MAX/2;
n /= 2;
while(n) {
seg1[n] = max(seg1[2*n],seg1[2*n+1]);
seg2[n] = max(seg2[2*n],seg2[2*n+1]);
seg3[n] = 1LL * seg3[2*n] * seg3[2*n+1] % p;
n /= 2;
}
}
int sum1(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg1[n];
int mid = ns + ne >> 1;
return max(sum1(s,e,2*n,ns,mid),sum1(s,e,2*n+1,mid,ne));
}
int sum2(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg2[n];
int mid = ns + ne >> 1;
return max(sum2(s,e,2*n,ns,mid),sum2(s,e,2*n+1,mid,ne));
}
int sum3(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return 1;
if(s<=ns&&ne<=e) return seg3[n];
int mid = ns + ne >> 1;
return 1LL * sum3(s,e,2*n,ns,mid)*sum3(s,e,2*n+1,mid,ne) % p;
}
int sum1(int s, int e) {
if(s >= e) return 0;
return sum1(s, e, 1, 0, MAX/2);
}
int sum2(int s, int e) {
if(s >= e) return 0;
return sum2(s, e, 1, 0, MAX/2);
}
int sum3(int s, int e) {
if(s >= e) return 1;
return sum3(s, e, 1, 0, MAX/2);
}
void Edit(int t, int n, int a) {
if(t == 1) {
seg1[n+MAX/2] = a;
seg3[n+MAX/2] = a;
}
if(t == 2) seg2[n+MAX/2] = a;
update(n);
}
P get_left(int k) {
int n = k + MAX/2 - 1;
if(k == 0) return P(k, 0);
while(n) {
//cout << n << ' ';
if(seg1[n] != 1) break;
while(n % 2 == 0) {
n /= 2;
}
n ^= 1;
}
//cout << '\n';
if(n == 0) {
return P(0, sum2(0, k));
}
while(n < MAX/2) {
if(seg1[2*n+1] != 1) n = 2*n + 1;
else n = 2*n;
}
n -= MAX/2;
n++;
return P(n, sum2(n, k));
}
};
SegTree tree;
int N;
vector<int> X, Y;
int init(int N2, int X2[], int Y2[]) {
N = N2;
for(int i = 0; i < N; i++) {
X.push_back(X2[i]);
Y.push_back(Y2[i]);
}
tree.init(N+5);
//cout << "st\n";
int MAX = tree.MAX;
int i, j;
for(i=0;i<N;i++) {
tree.seg1[i+MAX/2] = X[i];
tree.seg2[i+MAX/2] = Y[i];
tree.seg3[i+MAX/2] = X[i];
}
tree.cons();
//cout <<"st2\n";
long long int cnt = 1;
int pt = N;
long long int macnt = 1;
int ma = 0;
int ans = 0;
while(pt >= 0 && cnt <= 1e9) {
P k = tree.get_left(pt);
//cout << pt << ' ' << k.first << ' ' << k.second << '\n';
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
macnt = cnt;
ma = k.second;
ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
}
if(pt < 0) break;
if(macnt * Y[pt] > cnt * ma) {
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
}
return ans;
}
int updateX(int pos, int val) {
tree.Edit(1,pos,val);
X[pos] = val;
long long int cnt = 1;
int pt = N;
long long int macnt = 1;
int ma = 0;
int ans = 0;
while(pt >= 0 && cnt <= 1e9) {
P k = tree.get_left(pt);
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
macnt = cnt;
ma = k.second;
ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
}
if(pt < 0) break;
if(macnt * Y[pt] > cnt * ma) {
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
}
return ans;
}
int updateY(int pos, int val) {
tree.Edit(2, pos, val);
Y[pos] = val;
long long int cnt = 1;
int pt = N;
long long int macnt = 1;
int ma = 0;
int ans = 0;
while(pt >= 0 && cnt <= 1e9) {
P k = tree.get_left(pt);
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
macnt = cnt;
ma = k.second;
ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
}
if(pt < 0) break;
if(macnt * Y[pt] > cnt * ma) {
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In member function 'void SegTree::cons()':
horses.cpp:21:53: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
21 | seg3[i] = 1LL * seg3[2*i] * seg3[2*i+1] % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In member function 'void SegTree::update(int)':
horses.cpp:30:53: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
30 | seg3[n] = 1LL * seg3[2*n] * seg3[2*n+1] % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In member function 'int SegTree::sum1(int, int, int, int, int)':
horses.cpp:37:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = ns + ne >> 1;
| ~~~^~~~
horses.cpp: In member function 'int SegTree::sum2(int, int, int, int, int)':
horses.cpp:43:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = ns + ne >> 1;
| ~~~^~~~
horses.cpp: In member function 'int SegTree::sum3(int, int, int, int, int)':
horses.cpp:49:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid = ns + ne >> 1;
| ~~~^~~~
horses.cpp:50:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
50 | return 1LL * sum3(s,e,2*n,ns,mid)*sum3(s,e,2*n+1,mid,ne) % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:121:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
121 | while(pt >= 0 && cnt <= 1e9) {
| ^~~
horses.cpp:128:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
128 | ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:134:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
134 | ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:108:12: warning: unused variable 'j' [-Wunused-variable]
108 | int i, j;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:148:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
148 | while(pt >= 0 && cnt <= 1e9) {
| ^~~
horses.cpp:154:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
154 | ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:160:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
160 | ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:174:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
174 | while(pt >= 0 && cnt <= 1e9) {
| ^~~
horses.cpp:180:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
180 | ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:186:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
186 | ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |