| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 483950 | Cross_Ratio | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 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;
if(k == 0 || seg[k-1+MAX/2] != 1) return P(k, 0);
while(n) {
//cout << n << ' ';
if(seg1[n] != 1) break;
n /= 2;
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;
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;
}