oj.uz

Submission #761912

# Submission time Handle Problem Language Result Execution time Memory
761912 2023-06-20T11:27:07 Z Ahmed57 Horses (IOI15_horses) C++17
34 / 100
 796 ms 46972 KB 
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
//Fast
long long fast(long long a,long long b){
    if(b==0)return 1;
    if(b==1)return a%mod;
    long long ha = fast(a,b/2)%mod;
    if(b%2==0)return (ha*ha)%mod;
    else return (((ha*ha)%mod)*a)%mod;
}
long long seg[2000001],lazy[2000001];
double seg2[2000001],lazy2[2000001];
void prop(int p,int l,int r){
    seg[p]*=lazy[p];
    seg[p]%=mod;
    seg2[p]+=lazy2[p];
    if(l!=r){
        lazy[p*2]*=lazy[p];
        lazy[p*2]%=mod;
        lazy2[p*2]+=lazy2[p];
        lazy[p*2+1]*=lazy[p];
        lazy[p*2+1]%=mod;
        lazy2[p*2+1]+=lazy2[p];
    }
    lazy[p] = 1;
    lazy2[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val,double val2){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]*=val;
        lazy[p]%=mod;
        lazy2[p]+=val2;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val,val2);
    update(p*2+1,md+1,r,lq,rq,val,val2);
    if(seg2[p*2]>seg2[p*2+1]){
        seg2[p]= seg2[p*2];
        seg[p] = seg[p*2];
    }else{
        seg2[p]= seg2[p*2+1];
        seg[p] = seg[p*2+1];
    }
}
pair<long long,double> query(int p,int l,int r,int lq,int rq){
    prop(p,l,r);
    if(l>=lq&&r<=rq)return {seg[p],seg2[p]};
    if(l>rq||r<lq)return {0,-1};
    int md = (l+r)/2;
    pair<long long,double> p1 = query(p*2,l,md,lq,rq);
    pair<long long,double> p2 = query(p*2+1,md+1,r,lq,rq);
    if(p1.second>p2.second)return p1;
    else return p2;
}
int n;
vector<long long> x,y;
long long init(int N,int X[],int Y[]){
    n = N;
    for(int i = 0;i<=8e5;i++){
        seg[i] = 1, lazy[i] = 1;
        seg2[i] = 0 , lazy2[i] = 0;
    }
    for(int i = 0;i<n;i++){
        x.push_back(X[i]);
        y.push_back(Y[i]);
        update(1,1,n,i+1,n,X[i],log(X[i]));
        update(1,1,n,i+1,i+1,Y[i],log(Y[i]));
    }
    return query(1,1,n,1,n).first;
}long long updateX(int pos,int val){
     update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log(x[pos]));
     x[pos] = val;
     update(1,1,n,pos+1,n,x[pos],log(x[pos]));
     return query(1,1,n,1,n).first;
}long long updateY(int pos,int val){
     update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log(y[pos]));
     y[pos] = val;
     update(1,1,n,pos+1,pos+1,y[pos],log(y[pos]));
     return query(1,1,n,1,n).first;
}/*
int main(){
    int X[] = {2,1,3};
    int Y[] = {3,4,1};
    cout<<init(3,X,Y)<<endl;
    cout<<updateX(0,1)<<endl;
}*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 9 ms 25300 KB Output is correct
3 Correct 9 ms 25300 KB Output is correct
4 Correct 9 ms 25384 KB Output is correct
5 Correct 11 ms 25288 KB Output is correct
6 Correct 9 ms 25300 KB Output is correct
7 Correct 10 ms 25300 KB Output is correct
8 Correct 9 ms 25300 KB Output is correct
9 Correct 10 ms 25308 KB Output is correct
10 Correct 10 ms 25268 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 10 ms 25256 KB Output is correct
13 Correct 12 ms 25300 KB Output is correct
14 Correct 9 ms 25300 KB Output is correct
15 Correct 9 ms 25300 KB Output is correct
16 Correct 11 ms 25360 KB Output is correct
17 Correct 9 ms 25356 KB Output is correct
18 Correct 9 ms 25300 KB Output is correct
19 Correct 12 ms 25300 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25300 KB Output is correct
2 Correct 10 ms 25324 KB Output is correct
3 Correct 9 ms 25388 KB Output is correct
4 Correct 10 ms 25300 KB Output is correct
5 Correct 9 ms 25300 KB Output is correct
6 Correct 11 ms 25268 KB Output is correct
7 Correct 10 ms 25300 KB Output is correct
8 Correct 10 ms 25332 KB Output is correct
9 Correct 9 ms 25300 KB Output is correct
10 Correct 9 ms 25324 KB Output is correct
11 Correct 10 ms 25264 KB Output is correct
12 Correct 9 ms 25304 KB Output is correct
13 Correct 10 ms 25300 KB Output is correct
14 Correct 10 ms 25360 KB Output is correct
15 Correct 9 ms 25300 KB Output is correct
16 Correct 9 ms 25292 KB Output is correct
17 Correct 10 ms 25268 KB Output is correct
18 Correct 9 ms 25300 KB Output is correct
19 Correct 10 ms 25384 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct
21 Correct 10 ms 25384 KB Output is correct
22 Correct 10 ms 25300 KB Output is correct
23 Correct 14 ms 25348 KB Output is correct
24 Correct 14 ms 25300 KB Output is correct
25 Correct 11 ms 25420 KB Output is correct
26 Correct 12 ms 25348 KB Output is correct
27 Correct 12 ms 25300 KB Output is correct
28 Correct 11 ms 25300 KB Output is correct
29 Correct 11 ms 25300 KB Output is correct
30 Correct 11 ms 25380 KB Output is correct
31 Correct 11 ms 25404 KB Output is correct
32 Correct 11 ms 25316 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 796 ms 46968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25300 KB Output is correct
2 Correct 11 ms 25300 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 11 ms 25324 KB Output is correct
5 Correct 9 ms 25300 KB Output is correct
6 Correct 10 ms 25336 KB Output is correct
7 Correct 10 ms 25300 KB Output is correct
8 Correct 10 ms 25272 KB Output is correct
9 Correct 10 ms 25300 KB Output is correct
10 Correct 9 ms 25300 KB Output is correct
11 Correct 9 ms 25300 KB Output is correct
12 Correct 9 ms 25300 KB Output is correct
13 Correct 12 ms 25300 KB Output is correct
14 Correct 10 ms 25300 KB Output is correct
15 Correct 9 ms 25300 KB Output is correct
16 Correct 10 ms 25296 KB Output is correct
17 Correct 9 ms 25300 KB Output is correct
18 Correct 10 ms 25348 KB Output is correct
19 Correct 10 ms 25260 KB Output is correct
20 Correct 9 ms 25300 KB Output is correct
21 Correct 12 ms 25340 KB Output is correct
22 Correct 9 ms 25364 KB Output is correct
23 Correct 11 ms 25300 KB Output is correct
24 Correct 11 ms 25376 KB Output is correct
25 Correct 12 ms 25300 KB Output is correct
26 Correct 12 ms 25300 KB Output is correct
27 Correct 12 ms 25408 KB Output is correct
28 Correct 11 ms 25352 KB Output is correct
29 Correct 12 ms 25332 KB Output is correct
30 Correct 13 ms 25384 KB Output is correct
31 Correct 13 ms 25300 KB Output is correct
32 Correct 11 ms 25412 KB Output is correct
33 Incorrect 646 ms 45092 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25316 KB Output is correct
2 Correct 9 ms 25300 KB Output is correct
3 Correct 9 ms 25300 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 10 ms 25276 KB Output is correct
6 Correct 10 ms 25300 KB Output is correct
7 Correct 10 ms 25304 KB Output is correct
8 Correct 11 ms 25300 KB Output is correct
9 Correct 10 ms 25428 KB Output is correct
10 Correct 10 ms 25316 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 11 ms 25300 KB Output is correct
13 Correct 11 ms 25328 KB Output is correct
14 Correct 10 ms 25300 KB Output is correct
15 Correct 10 ms 25348 KB Output is correct
16 Correct 11 ms 25300 KB Output is correct
17 Correct 9 ms 25264 KB Output is correct
18 Correct 9 ms 25304 KB Output is correct
19 Correct 9 ms 25300 KB Output is correct
20 Correct 10 ms 25264 KB Output is correct
21 Correct 10 ms 25300 KB Output is correct
22 Correct 10 ms 25344 KB Output is correct
23 Correct 11 ms 25372 KB Output is correct
24 Correct 11 ms 25300 KB Output is correct
25 Correct 11 ms 25384 KB Output is correct
26 Correct 11 ms 25408 KB Output is correct
27 Correct 11 ms 25300 KB Output is correct
28 Correct 11 ms 25412 KB Output is correct
29 Correct 11 ms 25300 KB Output is correct
30 Correct 13 ms 25340 KB Output is correct
31 Correct 13 ms 25300 KB Output is correct
32 Correct 11 ms 25396 KB Output is correct
33 Incorrect 791 ms 46972 KB Output isn't correct
34 Halted 0 ms 0 KB -