Submission #955482

# Submission time Handle Problem Language Result Execution time Memory
955482 2024-03-30T14:31:39 Z PoPularPlusPlus Horses (IOI15_horses) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 500003 , L = 70;

struct Seg {
	
	int siz;
	vector<ll> sum;
	
	ll Nutral = 1;
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		siz *= 2;
		sum.resize(siz * 2 , Nutral);
	}
	
	void build(vector<int>& a , int x,  int lx , int rx){
		if(rx - lx == 1){
			if(lx < (int)a.size())sum[x] = a[lx];
			return;
		}
		int m = (lx + rx)/2;
		build(a , 2 * x + 1 , lx , m);
		build(a , 2 * x + 2 , m , rx);
		sum[x] = (sum[2 * x + 1] * sum[2 * x + 2])%mod;
	}
	
	void build(vector<int>& a){
		return build(a , 0 , 0 , siz);
	}
	
	void set(int i , int v ,int x , int lx , int rx){
		if(rx - lx == 1){
			sum[x] = v;
			return;
		}
		int m = (lx + rx)/2;
		if(i < m){
			set(i , v , 2 * x + 1 , lx , m);
		}
		else set(i , v , 2 * x + 2 , m , rx);
		sum[x] = (sum[2 * x + 1] * sum[2 * x + 2])%mod;
	}
	
	void set(int i , int v){
		set(i , v , 0 , 0 , siz);
	}
	
	int sums(int l , int r , int x , int lx , int rx){
		if(l >= rx || r <= lx)return Nutral;
		if(lx >= l && rx <= r)return sum[x];
		int m = (lx + rx)/2;
		return (sums(l , r , 2 * x +  1 , lx , m) * sums(l , r  , 2 * x +2 , m , rx))%mod;
	}
	
	int sums(int l , int r){
		return sums(l , r , 0 , 0 , siz);
	}
};


struct SegMX {
	vector<ll> v;
	int siz;

	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		v.assign(siz * 2 , 0);
	}

	void build(vector<int>& a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < a.size()){
				v[x] = a[lx];
			}
			return;
		}
		int m = (lx + rx)/2;
		build(a , 2*x+1,lx,m);
		build(a , 2 * x + 2 , m , rx);
		v[x] = max(v[2 * x + 1] , v[2*x+2]);
	}

	void build(vector<int>& a){
		buld(a , 0 , 0 , siz);
	}

	void set(int i , int val , int x , int lx, int rx){
		if(rx - lx == 1){
			v[x] = val;
			return;
		}
		int m = (lx + rx)/2;
		if(i < m){
			set(i , val ,2 * x + 1 , lx ,m);
		}
		else {
			set(i , val , 2 * x + 2, m , rx);
		}
		v[x] = max(v[2*x+1] , v[2*x+2]);
	}

	void set(int i , int val){
		set(i , val , 0 , 0, siz);
	}

	ll find(int l , int r , int x , int lx, int rx){
		if(lx >= r || l >= rx)return 0;
		if(lx >= l && rx <= r)return v[x];
		int m = (lx + rx)/2;
		return max(find(l,r,2*x+1,lx,m),find(l , r , 2 * x + 2 , m ,rx));
	}

	ll find(int l , int r){
		return find(l , r , 0 , 0 , siz);
	}
};

int n;
vector<int> x,y;
set<int> s,s1;
SegMX st;
Seg st_sum;
vector<pair<int,ll>> last;

int cal(){
	int pos = -1;
	ll multi = 1;
	if(v.size() < L){
		int right = n;
		auto it = s.upper_bound(0);
		if(it != s.end()){
			right = *it;
		}
		cur = st.find(0,right);
		if(v.size()){
			int idx = v[0].vf;
			if(x[idx] * v[0].vs >= cur){
				pos = 0;
			}
			else {
				multi *= x[idx];
			}
		}
	}
	for(int i = 1; i < v.size(); i++){
		int idx = v[i].vf;
		if(multi >= 1e9){
			pos = i;
			multi = 1;
		}
		else {
			if(x[idx] * v[i].vs >= v[i-1].vs){
				pos = i;
			}
			else {
				multi *= x[idx];
			}
		}
	}
	return (st_sum(x[v[pos].vf] + 1) * v[pos].vs) % mod;
}

int init(int n1 , vector<int> x1 , vector<int> y1){
	n = n1;
	x = x1;
	y = y1;

	s.insert(0);
	for(int i = 0; i < n; i++){
		if(x[i] > 1){
			s.insert(i);
		}
	}

	st.init(n + 1);
	st.build(y);
	st_sum.init(n + 1);
	st_sum.build(y);

	for(int i = n - 1; i >= 0 && v.size() < L; i--){
		if(x[i] > 1){
			auto it = s.upper_bound(i);
			int right = i;
			if(it == s.end()){
				right = n;
			}
			else right = (*it);

			v.pb(mp(i,st.find(i,right)));
		}
	}

	reverse(all(v));

	return cal();
}

int updateX(int pos , int val){
	pos--;
	int toerase = -1;
	for(int i = 0; i < v.size() && val == 1; i++){
		if(x[v[i].vf] == pos){
			toerase = i;
			break;
		}
	}
	if(toerase != -1){
		v.erase(v.begin()+toerase);
		s.erase(toerase);
		if(v.size()){
			auto it = s.lower_bound(toerase);
			if(it != s.begin()){
				auto it1 = it;
				it--;
				vector<pair<int,ll>> v1;
				v1.pb(mp(*it,st.find(*it,*it1)));
				for(auto tp : v){
					v1.pb(tp);
				}
				v = v1;
			}
		}
	}
	else {
		if(val == 1 && s.find(pos)!=s.end()){
			return cal();
		}
		if(val > 1)s.insert(pos);
		if(v.size() == 0 || pos > x[v[0].vf]){
			v.erase(v.begin());
			auto it = s.upper_bound(pos);
			int right = n;
			if(it!=s.end()){
				right = *it;
			}
			v.pb(mp(pos , st.find(pos , right)));
		}
	}
	st_sum.set(pos , val);

	return cal();
}

int updateY(int pos , int val){
	pos--;
	st.set(pos , val);
	if(v.size() && ix[v[0].vf] <= pos){
		int cur = 0;
		for(int i = 0; i < v.size() && x[v[i].vf] <= pos; i++){
			cur = i;
		}
		int right = n;
		if(cur + 1 < v.size()){
			right = x[v[cur+1].vf];
			v[cur].vs = st.find(x[v[i].vf] , right);
		}
	}

	return cal();
}

void solve(){
	int n;
	cin >> n;
	vector<int> a, b;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		a.pb(x);
	}
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		b.pb(x);
	}
	int m;
	cin >> m;
	cout << init(n , a , b) << '\n';
	while(m--){
		int t;
		cin >> t;
		int pos , val;
		cin >> pos >> val;
		if(t == 1){
			cout<< updateX(pos , val) << '\n';
		}
		else cout << updateY(pos , val) << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin>>t;
	//while(t--) 
	solve();
	return 0;
}

Compilation message

horses.cpp: In member function 'int Seg::sums(int, int, int, int, int)':
horses.cpp:62:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |   if(l >= rx || r <= lx)return Nutral;
      |                                ^~~~~~
horses.cpp:63:37: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   63 |   if(lx >= l && rx <= r)return sum[x];
      |                                     ^
horses.cpp: In member function 'void SegMX::build(std::vector<int>&, int, int, int)':
horses.cpp:86:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    if(lx < a.size()){
      |       ~~~^~~~~~~~~~
horses.cpp: In member function 'void SegMX::build(std::vector<int>&)':
horses.cpp:98:3: error: 'buld' was not declared in this scope; did you mean 'build'?
   98 |   buld(a , 0 , 0 , siz);
      |   ^~~~
      |   build
horses.cpp: In function 'int cal()':
horses.cpp:142:5: error: 'v' was not declared in this scope
  142 |  if(v.size() < L){
      |     ^
horses.cpp:148:3: error: 'cur' was not declared in this scope
  148 |   cur = st.find(0,right);
      |   ^~~
horses.cpp:159:21: error: 'v' was not declared in this scope
  159 |  for(int i = 1; i < v.size(); i++){
      |                     ^
horses.cpp:161:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  161 |   if(multi >= 1e9){
      |      ^~~~~
horses.cpp:174:19: error: 'v' was not declared in this scope
  174 |  return (st_sum(x[v[pos].vf] + 1) * v[pos].vs) % mod;
      |                   ^
horses.cpp: In function 'int init(int, std::vector<int>, std::vector<int>)':
horses.cpp:194:31: error: 'v' was not declared in this scope
  194 |  for(int i = n - 1; i >= 0 && v.size() < L; i--){
      |                               ^
horses.cpp:207:14: error: 'v' was not declared in this scope
  207 |  reverse(all(v));
      |              ^
horses.cpp:6:16: note: in definition of macro 'all'
    6 | #define all(x) x.begin(),x.end()
      |                ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:215:21: error: 'v' was not declared in this scope
  215 |  for(int i = 0; i < v.size() && val == 1; i++){
      |                     ^
horses.cpp:222:3: error: 'v' was not declared in this scope
  222 |   v.erase(v.begin()+toerase);
      |   ^
horses.cpp:243:6: error: 'v' was not declared in this scope
  243 |   if(v.size() == 0 || pos > x[v[0].vf]){
      |      ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:261:5: error: 'v' was not declared in this scope
  261 |  if(v.size() && ix[v[0].vf] <= pos){
      |     ^
horses.cpp:261:17: error: 'ix' was not declared in this scope; did you mean 'x'?
  261 |  if(v.size() && ix[v[0].vf] <= pos){
      |                 ^~
      |                 x
horses.cpp:269:28: error: 'i' was not declared in this scope
  269 |    v[cur].vs = st.find(x[v[i].vf] , right);
      |                            ^
horses.cpp: In function 'void solve()':
horses.cpp:277:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  277 |  int n;
      |      ^
horses.cpp:132:5: note: shadowed declaration is here
  132 | int n;
      |     ^
horses.cpp:281:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  281 |   int x;
      |       ^
horses.cpp:133:13: note: shadowed declaration is here
  133 | vector<int> x,y;
      |             ^
horses.cpp:286:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  286 |   int x;
      |       ^
horses.cpp:133:13: note: shadowed declaration is here
  133 | vector<int> x,y;
      |             ^