oj.uz

Submission #1013655

# Submission time Handle Problem Language Result Execution time Memory
1013655 2024-07-03T18:30:01 Z Mardonbekhazratov Horses (IOI15_horses) C++17
20 / 100
 278 ms 43420 KB 
#include "horses.h"
#include<algorithm>
#include<vector>
#include<iostream>
#include<set>
const long long INFLL=1e18;
const int INF=1e9;
const int MOD=1e9+7;

using namespace std;

struct SegTree{
    int N;
    const int NEU=0;
    vector<int>tree;

    int merge(int a,int b){
        return max(a,b);
    }

    void build(vector<int>&a){
        N=1;
        int n=a.size();
        while(N<n) N<<=1;

        tree.assign(N<<1,NEU);
        for(int i=0;i<n;i++) tree[i+N]=a[i];
        for(int i=N-1;i>0;i--) tree[i]=merge(tree[i<<1],tree[i<<1|1]);
    }

    void update(int v,int l,int r,int id,int x){
        if(l>id || id>=r) return;
        if(r-l==1){
            tree[v]=x;
            return;
        }

        int mid=(l+r)>>1;
        update(v<<1,l,mid,id,x);
        update(v<<1|1,mid,r,id,x);

        tree[v]=merge(tree[v<<1],tree[v<<1|1]);
    }

    void update(int id,int x){
        return update(1,0,N,id,x);
    }

    int get(int v,int l,int r,int ql,int qr){
        if(l>=qr || ql>=r) return NEU;
        if(l>=ql && qr>=r) return tree[v];

        int mid=(l+r)>>1;
        int a=get(v<<1,l,mid,ql,qr);
        int b=get(v<<1|1,mid,r,ql,qr);
        return merge(a,b);
    }

    int get(int l,int r){
        return get(1,0,N,l,r);
    }
};

int inv(int x){
	return x>1 ? MOD-(long long)(MOD/x)*inv(MOD%x)%MOD : x;
}

int n;
vector<int>x,y;
set<int>p;

SegTree S;
long long pref;

int get(){
	long long ans=1;
	long long pr=pref;
	int last=n;
	for(int i:p){
		i=n-i;
		ans=max(ans,1LL*S.get(i,last));
		last=i;
		if(ans>=INF){
			ans%=MOD;
			return pr*ans%MOD;
		}
		ans*=x[i];
		pr=pr*inv(x[i])%MOD;
	}
	return ans*pr%MOD;
}

int init(int N, int X[], int Y[]) {
	n=N;
	pref=1;
	x.resize(n);
	y.resize(n);
	for(int i=0;i<n;i++){
		x[i]=X[i],y[i]=Y[i];
		pref=pref*x[i]%MOD;
		if(x[i]>1) p.insert(n-i);
	}
	S.build(y);
	return get();
}


int updateX(int pos, int val) {	
	if(x[pos]>1) p.erase(n-pos);
	pref=pref*inv(x[pos])%MOD*val%MOD;
	x[pos]=val;
	if(x[pos]>1) p.insert(n-pos);
	return get();
}

int updateY(int pos, int val) {
	S.update(pos,val);
	return get();
}

Compilation message

horses.cpp: In member function 'void SegTree::build(std::vector<int>&)':
horses.cpp:23:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |         int n=a.size();
      |               ~~~~~~^~
horses.cpp: In function 'int inv(int)':
horses.cpp:65:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |  return x>1 ? MOD-(long long)(MOD/x)*inv(MOD%x)%MOD : x;
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:85:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |    return pr*ans%MOD;
      |           ~~~~~~^~~~
horses.cpp:90:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans*pr%MOD;
      |         ~~~~~~^~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 39192 KB Output is correct
2 Correct 192 ms 43420 KB Output is correct
3 Correct 205 ms 38740 KB Output is correct
4 Correct 238 ms 40772 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -