oj.uz

답안 #761879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761879 2023-06-20T10:52:29 Z Ahmed57 말 (IOI15_horses) C++17
0 / 100
 380 ms 524288 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];
long long seg2[800001],lazy2[800001];
long long 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,long long 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,long long> 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,long long> p1 = query(p*2,l,md,lq,rq);
    pair<long long,long long> p2 = query(p*2+1,md+1,r,lq,rq);
    if(p1.second>p2.second)return p1;
    else return p2;
}
int n;
vector<int> x,y;
void 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],log2(X[i]));
        update(1,1,n,i+1,i+1,Y[i],log2(Y[i]));
    }
    cout<<query(1,1,n,1,n).first<<endl;
}
long long updateX(int pos,int val){
     update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log2(x[pos]));
     x[pos] = val;
     update(1,1,n,pos+1,n,x[pos],log2(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),-log2(y[pos]));
     y[pos] = val;
     update(1,1,n,pos+1,pos+1,y[pos],log2(y[pos]));
     return query(1,1,n,1,n).first;
}/*
int main(){
    init(3,{2,1,3},{3,4,1});
    cout<<updateX(0,1)<<endl;
}*/

Compilation message

horses.cpp: In function 'long long int prop(int, int, int)':
horses.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
horses.cpp: In function 'void init(int, int*, int*)':
horses.cpp:71:37: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   71 |         update(1,1,n,i+1,n,X[i],log2(X[i]));
      |                                 ~~~~^~~~~~
horses.cpp:72:39: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   72 |         update(1,1,n,i+1,i+1,Y[i],log2(Y[i]));
      |                                   ~~~~^~~~~~
horses.cpp: In function 'long long int updateX(int, int)':
horses.cpp:77:46: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   77 |      update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log2(x[pos]));
      |                                              ^~~~~~~~~~~~~
horses.cpp:79:38: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   79 |      update(1,1,n,pos+1,n,x[pos],log2(x[pos]));
      |                                  ~~~~^~~~~~~~
horses.cpp: In function 'long long int updateY(int, int)':
horses.cpp:82:50: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   82 |      update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log2(y[pos]));
      |                                                  ^~~~~~~~~~~~~
horses.cpp:84:42: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
   84 |      update(1,1,n,pos+1,pos+1,y[pos],log2(y[pos]));
      |                                      ~~~~^~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 380 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 333 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 51 ms 61260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 302 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 299 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -