oj.uz

Submission #597155

# Submission time Handle Problem Language Result Execution time Memory
597155 2022-07-15T15:53:22 Z Apiram Horses (IOI15_horses) C++14
0 / 100
 252 ms 44540 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct dataa2{
	long long v = 0,index = 0;
	void add(long long val){
		v = val;
	}
};
struct dataa{
	long long v = 0;
	bool ok = 1;
	void add(long long val){
		v = val;
		//sum += val *(right - left + 1);
	}
};
struct Segment_Tree{
	vector<dataa>tree;
	void build(long long node,long long left,long long right,vector<long long>&arr,long long n){
		if (left == right){
			tree[node].v  = arr[left];
			return ;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		build(node + 1,left,mid,arr,n);
		build(z,mid + 1,right,arr,n);
		tree[node] = combine(tree[node + 1],tree[z]);
	}
	void init(long long n,vector<long long>&arr){
		tree.resize(2*n - 1);
		build(0,0,n-1,arr,n);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		res.v = (left.v * right.v)%mod;
		res.ok = left.ok & right.ok;
		if (res.ok){
			if (left.v * right.v > 1e9)res.ok = false;
		}
		return res;
	}
	dataa query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return {1,1};
		if (qleft<=left && qright>=right){
			return tree[node];
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			tree[node].add(v);
			return;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,v);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,v);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};
Segment_Tree st;
struct Segment_Tree2{
	vector<dataa2>tree;
	int N;
	void build(long long node,long long left,long long right,vector<long long>&arr,long long n){
		if (left == right){
			tree[node].v = arr[left];
			tree[node].index = left;
			return ;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		build(node + 1,left,mid,arr,n);
		build(z,mid + 1,right,arr,n);
		tree[node] = combine(tree[node + 1],tree[z]);
	}
	void init(long long n,vector<long long>&arr){
		tree.resize(2*n - 1);
		N = n;
		build(0,0,n-1,arr,n);
	}
	dataa2 combine(dataa2 left,dataa2 right){
		dataa2 res = right;
		auto temp = st.query(0,0,N - 1,left.index + 1,right.index);
		bool ok = temp.ok;
		if (left.v > right.v && (ok && temp.v * left.v <= right.v)){
			res = left;
		}
		return res;
	}
	dataa2 query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return {0,0};
		if (qleft<=left && qright>=right){
			return tree[node];
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			tree[node].add(v);
			return;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,v);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,v);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};
vector<long long>x,y;
Segment_Tree2 st2;
int solve(){
	int N = (int)x.size();
	auto temp = st2.query(0,0,N - 1,0,N - 1);
	return (st.query(0,0,N - 1,0,temp.index).v * temp.v)%mod;
}
int init(int N, int X[], int Y[]) {
	for (int i = 0;i<N;++i){
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	st.init(N,x);
	st2.init(N,y);
	return solve();
}

int updateX(int pos, int val) {	
	st.update(0,0,(int)x.size()-1,pos,pos,val);
	st2.update(0,0,(int)x.size() - 1,pos,pos,y[pos]);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	st2.update(0,0,(int)x.size() - 1,pos,pos,y[pos]);
	return solve();
}

Compilation message

horses.cpp: In member function 'dataa Segment_Tree::combine(dataa, dataa)':
horses.cpp:41:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   41 |    if (left.v * right.v > 1e9)res.ok = false;
      |        ~~~~~~~^~~~~~~~~
horses.cpp: In member function 'void Segment_Tree2::init(long long int, std::vector<long long int>&)':
horses.cpp:89:7: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |   N = n;
      |       ^
horses.cpp: In function 'int solve()':
horses.cpp:132:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  return (st.query(0,0,N - 1,0,temp.index).v * temp.v)%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -