| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 483885 | Cross_Ratio | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 s = 0, e = k+1;
while(s + 1 != e) {
int mid = s + e >> 1;
if(sum1(mid,k)==1) {
if(seg1[mid-1+MAX/2] >= 2) {
s = mid;
break;
}
else e = mid;
}
else s = mid+1;
}
return P(s,sum2(s,k));
}
};
SegTree tree;
int N;
vector<int> X, Y;
int init(int N2, vector<int> X2, vector<int> Y2) {
N = N2;
X = X2;
Y = Y2;
tree.init(N+5);
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();
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) {
//cout << "E1\n";
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) {
//cout << "E2\n";
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
//cout <<pt << ' ' << ans << '\n';
}
return ans;
}
int updateX(int pos, int val) {
tree.Edit(1,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);
//cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
//cout << "E1\n";
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) {
//cout << "E2\n";
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
//cout <<pt << ' ' << ans << '\n';
}
return ans;
}
int updateY(int pos, int val) {
tree.Edit(2, 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);
//cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
//cout << "E1\n";
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) {
//cout << "E2\n";
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
//cout <<pt << ' ' << ans << '\n';
}
return ans;
}