Submission #349023

#	Time	Username	Problem	Language	Result	Execution time	Memory
349023		Sprdalo	Horses (IOI15_horses)	C++17	17 / 100	107 ms	36296 KiB

horses

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

template<int maxn>
struct segtree{
	struct update{
		ld x;

		update(ld x = 0) : x(x) {}

		update& operator+= (const update& other){
			x += other.x;
			return *this;
		}

		update operator+ (const update& other){
			auto tmp = *this;
			return tmp += other;
		}

		operator bool() const{
			return x != 0;
		}
	};

	struct node{
		ld x;
		int l, r;

		node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}

		node& operator+= (const node& other){
			x = max(x, other.x);
			r = other.r;
			return *this;
		}

		node operator+ (const node& other){
			auto tmp = *this;
			return tmp += other;
		}

		node& operator+= (const update& other){
			x += other.x;
			return *this;
		}

		node operator+ (const update& other){
			auto tmp = *this;
			return tmp += other;
		}
	};

	node a[2*maxn];
	update lazy[2*maxn];

	void init(vector<ld> t){
		int n = t.size();
		for (int i = 1; i <= maxn; ++i)
			if (i <= n)
				a[i+maxn-1] = node{t[i-1], i, i};
			else
				a[i+maxn-1] = node{0, i, i};

		for (int i = maxn-1; i > 0; --i){
			a[i] = a[2*i] + a[2*i+1];
		}
	}

	void push(int i){
		if (lazy[i]){
			a[i] += lazy[i];

			if (i < maxn){
				lazy[2*i] += lazy[i];
				lazy[2*i+1] += lazy[i];
			}
			lazy[i] = update{0};
		}
	}

	node get(int l, int r, int pos = 1, int L = 1, int R = maxn){
		push(pos);
		if (l <= L && R <= r) return a[pos];
		if (L > r || l > R) return node{};

		int mid = (L+R)/2;

		return get(l,r,2*pos,L,mid) + get(l,r,2*pos+1,mid+1,R);
	}

	void add(int l, int r, update v, int pos = 1, int L = 1, int R = maxn){
		push(pos);
		if (l <= L && R <= r){
			lazy[pos] += v;
			push(pos);
			return;
		}	

		if (l > R || L > r)
			return;

		int mid = (L+R)/2;

		add(l,r,v,2*pos,L,mid);
		add(l,r,v,2*pos+1,mid+1,R);
		a[pos] = a[2*pos]+a[2*pos+1];
	}

	void print(){
		for (int i = 1; i < 2*maxn; ++i)
			cout << a[i].x << ' ';
	}
};
segtree<131072> drvo;

int n;
vi x, y;

int init(int N, int X[], int Y[]){
	n = N;
	for (int i = 0; i < n; ++i){
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}

	vd t;
	ld c = 0;
	for (int i = 0; i < n; ++i){
		c += log(x[i]*1.0) + log(y[i]*1.0);
		t.push_back(c);
		c -= log(y[i]*1.0);
	}
	
	drvo.init(t);

	return round(exp(drvo.get(1, n).x));
}

int updateX(int pos, int val){
	ld c = log(val)-log(x[pos]);
	x[pos] = val;
	drvo.add(pos+1,n,c);

	return round(exp(drvo.get(1,n).x));
}

int updateY(int pos, int val){
	ld c = log(val) - log(y[pos]);
	y[pos] = val;
	drvo.add(pos+1,pos+1,c);

	return round(exp(drvo.get(1,n).x));
}

int man()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	cerr.tie(nullptr);	

	int N;
	cin >> N;

	int X[N], Y[N];

	for (int i = 0; i < N; ++i)
		cin >> X[i];

	for (int i = 0; i < N; ++i)
		cin >> Y[i];

	cout << init(N,X,Y) << '\n';

	int M;
	cin >> M;

	for (int i = 0; i < M; ++i){
		int type, pos, val;
		cin >> type >> pos >> val;

		if (type == 1)
			cout << updateX(pos,val) << '\n';
		else
			cout << updateY(pos, val) << '\n';
	}
}

Compilation message (stderr)

horses.cpp: In constructor 'segtree<maxn>::update::update(ld)':
horses.cpp:23:20: warning: declaration of 'x' shadows a member of 'segtree<maxn>::update' [-Wshadow]
   23 |   update(ld x = 0) : x(x) {}
      |                    ^
horses.cpp:21:6: note: shadowed declaration is here
   21 |   ld x;
      |      ^
horses.cpp: In constructor 'segtree<maxn>::node::node(ld, int, int)':
horses.cpp:44:40: warning: declaration of 'r' shadows a member of 'segtree<maxn>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                        ^
horses.cpp:42:10: note: shadowed declaration is here
   42 |   int l, r;
      |          ^
horses.cpp:44:40: warning: declaration of 'l' shadows a member of 'segtree<maxn>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                        ^
horses.cpp:42:7: note: shadowed declaration is here
   42 |   int l, r;
      |       ^
horses.cpp:44:40: warning: declaration of 'x' shadows a member of 'segtree<maxn>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                        ^
horses.cpp:41:6: note: shadowed declaration is here
   41 |   ld x;
      |      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:151:14: warning: conversion from 'long double' to 'int' may change value [-Wfloat-conversion]
  151 |  return round(exp(drvo.get(1, n).x));
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:159:14: warning: conversion from 'long double' to 'int' may change value [-Wfloat-conversion]
  159 |  return round(exp(drvo.get(1,n).x));
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:167:14: warning: conversion from 'long double' to 'int' may change value [-Wfloat-conversion]
  167 |  return round(exp(drvo.get(1,n).x));
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int man()':
horses.cpp:202:1: warning: no return statement in function returning non-void [-Wreturn-type]
  202 | }
      | ^
horses.cpp: In instantiation of 'segtree<maxn>::node::node(ld, int, int) [with int maxn = 131072; ld = long double]':
horses.cpp:19:8:   required from here
horses.cpp:44:3: warning: declaration of 'r' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |   ^~~~
horses.cpp:42:10: note: shadowed declaration is here
   42 |   int l, r;
      |          ^
horses.cpp:44:3: warning: declaration of 'l' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |   ^~~~
horses.cpp:42:7: note: shadowed declaration is here
   42 |   int l, r;
      |       ^
horses.cpp:44:3: warning: declaration of 'x' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |   ^~~~
horses.cpp:41:6: note: shadowed declaration is here
   41 |   ld x;
      |      ^
horses.cpp:44:60: warning: declaration of 'r' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                                            ^
horses.cpp:42:10: note: shadowed declaration is here
   42 |   int l, r;
      |          ^
horses.cpp:44:60: warning: declaration of 'l' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                                            ^
horses.cpp:42:7: note: shadowed declaration is here
   42 |   int l, r;
      |       ^
horses.cpp:44:60: warning: declaration of 'x' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                                            ^
horses.cpp:41:6: note: shadowed declaration is here
   41 |   ld x;
      |      ^
horses.cpp:44:60: warning: declaration of 'r' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                                            ^
horses.cpp:42:10: note: shadowed declaration is here
   42 |   int l, r;
      |          ^
horses.cpp:44:60: warning: declaration of 'l' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                                            ^
horses.cpp:42:7: note: shadowed declaration is here
   42 |   int l, r;
      |       ^
horses.cpp:44:60: warning: declaration of 'x' shadows a member of 'segtree<131072>::node' [-Wshadow]
   44 |   node(ld x = 0, int l = 0, int r = 0) : x(x), l(l), r(r) {}
      |                                                            ^
horses.cpp:41:6: note: shadowed declaration is here
   41 |   ld x;
      |      ^
horses.cpp: In instantiation of 'segtree<maxn>::update::update(ld) [with int maxn = 131072; ld = long double]':
horses.cpp:19:8:   required from here
horses.cpp:23:3: warning: declaration of 'x' shadows a member of 'segtree<131072>::update' [-Wshadow]
   23 |   update(ld x = 0) : x(x) {}
      |   ^~~~~~
horses.cpp:21:6: note: shadowed declaration is here
   21 |   ld x;
      |      ^
horses.cpp:23:28: warning: declaration of 'x' shadows a member of 'segtree<131072>::update' [-Wshadow]
   23 |   update(ld x = 0) : x(x) {}
      |                            ^
horses.cpp:21:6: note: shadowed declaration is here
   21 |   ld x;
      |      ^
horses.cpp:23:28: warning: declaration of 'x' shadows a member of 'segtree<131072>::update' [-Wshadow]
   23 |   update(ld x = 0) : x(x) {}
      |                            ^
horses.cpp:21:6: note: shadowed declaration is here
   21 |   ld x;
      |      ^
horses.cpp: In instantiation of 'void segtree<maxn>::init(std::vector<long double>) [with int maxn = 131072]':
horses.cpp:149:13:   required from here
horses.cpp:72:17: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   72 |   int n = t.size();
      |           ~~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23