oj.uz

Submission #761911

# Submission time Handle Problem Language Result Execution time Memory
761911 2023-06-20T11:25:30 Z Ahmed57 Horses (IOI15_horses) C++17
34 / 100
 373 ms 71964 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[800001],lazy[800001];
double seg2[800001],lazy2[800001];
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 10 ms 25300 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 10 ms 25292 KB Output is correct
5 Correct 10 ms 25300 KB Output is correct
6 Correct 10 ms 25300 KB Output is correct
7 Correct 10 ms 25272 KB Output is correct
8 Correct 10 ms 25272 KB Output is correct
9 Correct 10 ms 25256 KB Output is correct
10 Correct 10 ms 25292 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 10 ms 25264 KB Output is correct
13 Correct 11 ms 25352 KB Output is correct
14 Correct 10 ms 25300 KB Output is correct
15 Correct 10 ms 25268 KB Output is correct
16 Correct 10 ms 25300 KB Output is correct
17 Correct 11 ms 25300 KB Output is correct
18 Correct 11 ms 25300 KB Output is correct
19 Correct 10 ms 25268 KB Output is correct
20 Correct 10 ms 25288 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25244 KB Output is correct
2 Correct 9 ms 25300 KB Output is correct
3 Correct 10 ms 25340 KB Output is correct
4 Correct 10 ms 25268 KB Output is correct
5 Correct 10 ms 25300 KB Output is correct
6 Correct 9 ms 25272 KB Output is correct
7 Correct 10 ms 25344 KB Output is correct
8 Correct 12 ms 25272 KB Output is correct
9 Correct 9 ms 25256 KB Output is correct
10 Correct 10 ms 25300 KB Output is correct
11 Correct 10 ms 25236 KB Output is correct
12 Correct 10 ms 25316 KB Output is correct
13 Correct 11 ms 25300 KB Output is correct
14 Correct 10 ms 25268 KB Output is correct
15 Correct 9 ms 25300 KB Output is correct
16 Correct 10 ms 25332 KB Output is correct
17 Correct 9 ms 25300 KB Output is correct
18 Correct 10 ms 25300 KB Output is correct
19 Correct 10 ms 25300 KB Output is correct
20 Correct 10 ms 25272 KB Output is correct
21 Correct 10 ms 25352 KB Output is correct
22 Correct 12 ms 25316 KB Output is correct
23 Correct 12 ms 25400 KB Output is correct
24 Correct 12 ms 25300 KB Output is correct
25 Correct 12 ms 25428 KB Output is correct
26 Correct 12 ms 25300 KB Output is correct
27 Correct 14 ms 25280 KB Output is correct
28 Correct 12 ms 25392 KB Output is correct
29 Correct 11 ms 25372 KB Output is correct
30 Correct 13 ms 25300 KB Output is correct
31 Correct 12 ms 25300 KB Output is correct
32 Correct 14 ms 25400 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 ms 68020 KB Execution killed with signal 11
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 9 ms 25300 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 10 ms 25272 KB Output is correct
6 Correct 9 ms 25300 KB Output is correct
7 Correct 9 ms 25300 KB Output is correct
8 Correct 9 ms 25300 KB Output is correct
9 Correct 10 ms 25364 KB Output is correct
10 Correct 10 ms 25300 KB Output is correct
11 Correct 9 ms 25300 KB Output is correct
12 Correct 10 ms 25300 KB Output is correct
13 Correct 9 ms 25288 KB Output is correct
14 Correct 9 ms 25300 KB Output is correct
15 Correct 9 ms 25300 KB Output is correct
16 Correct 10 ms 25300 KB Output is correct
17 Correct 10 ms 25300 KB Output is correct
18 Correct 10 ms 25308 KB Output is correct
19 Correct 10 ms 25300 KB Output is correct
20 Correct 10 ms 25276 KB Output is correct
21 Correct 11 ms 25312 KB Output is correct
22 Correct 10 ms 25264 KB Output is correct
23 Correct 13 ms 25396 KB Output is correct
24 Correct 11 ms 25404 KB Output is correct
25 Correct 12 ms 25304 KB Output is correct
26 Correct 12 ms 25300 KB Output is correct
27 Correct 12 ms 25348 KB Output is correct
28 Correct 12 ms 25300 KB Output is correct
29 Correct 11 ms 25400 KB Output is correct
30 Correct 12 ms 25320 KB Output is correct
31 Correct 11 ms 25284 KB Output is correct
32 Correct 14 ms 25400 KB Output is correct
33 Runtime error 373 ms 71964 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 10 ms 25252 KB Output is correct
5 Correct 10 ms 25300 KB Output is correct
6 Correct 10 ms 25272 KB Output is correct
7 Correct 10 ms 25272 KB Output is correct
8 Correct 10 ms 25300 KB Output is correct
9 Correct 10 ms 25300 KB Output is correct
10 Correct 10 ms 25300 KB Output is correct
11 Correct 11 ms 25268 KB Output is correct
12 Correct 12 ms 25312 KB Output is correct
13 Correct 12 ms 25300 KB Output is correct
14 Correct 10 ms 25300 KB Output is correct
15 Correct 12 ms 25300 KB Output is correct
16 Correct 9 ms 25268 KB Output is correct
17 Correct 10 ms 25300 KB Output is correct
18 Correct 10 ms 25296 KB Output is correct
19 Correct 10 ms 25324 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct
21 Correct 10 ms 25300 KB Output is correct
22 Correct 10 ms 25300 KB Output is correct
23 Correct 12 ms 25300 KB Output is correct
24 Correct 12 ms 25300 KB Output is correct
25 Correct 12 ms 25388 KB Output is correct
26 Correct 12 ms 25408 KB Output is correct
27 Correct 12 ms 25300 KB Output is correct
28 Correct 12 ms 25300 KB Output is correct
29 Correct 12 ms 25300 KB Output is correct
30 Correct 13 ms 25372 KB Output is correct
31 Correct 11 ms 25348 KB Output is correct
32 Correct 14 ms 25300 KB Output is correct
33 Runtime error 359 ms 70168 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -