oj.uz

Submission #235112

# Submission time Handle Problem Language Result Execution time Memory
235112 2020-05-27T06:02:47 Z anubhavdhar Horses (IOI15_horses) C++14
54 / 100
 1033 ms 91040 KB 
#include<bits/stdc++.h>
#include "horses.h"
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
/*
const short int __PRECISION = 10;
 
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 5e5+5;
const ll ROOTN = 320;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/
#define MOD 1000000007
#define MAXN 500005
#define log2 111*log2
int x[MAXN], y[MAXN];
 
struct Segtree_aux
{
	ll st[4*MAXN];
 
	void upd(int node, int ss, int se, int i, ll val)
	{
		if(ss > i or se < i)
			return;
		if(ss == se)
		{
			st[node] = val % MOD;
			return;
		}
		int mid = (ss + se)/2;
		upd(node*2+1, ss, mid, i, val);
		upd(node*2+2, mid + 1, se, i, val);
		st[node] = (st[node*2+1] * st[node*2+2]) % MOD;
	}
 
	ll quer(int node, int ss, int se, int l, int r)
	{
		if(ss > r or se < l)
			return 1;
		if(ss >= l and se <= r)
			return st[node];
		int mid = (ss + se)/2;
		return (quer(node*2+1, ss, mid, l, r) * quer(node*2+2, mid + 1, se, l, r)) % MOD;
	}
 
	Segtree_aux()
	{
		F0R(i, 4*MAXN)
			st[i] = 1;
	}
 
	inline void update(int i, ll val)
	{
		upd(0, 0, MAXN, i, val);
	}
 
	inline ll query(int i)
	{
		return quer(0, 0, MAXN, 0, i);
	}
} aux;
 
struct Segtree_main
{
	ldd st[4*MAXN], lz[4*MAXN];
 
	inline void push(int node, int ss, int se)
	{
		if(lz[node] == 0)
			return;
		// else
			// cout<<"lz["<<ss<<','<<se<<"] = "<<lz[node]<<'\n';
		st[node] += lz[node];
		// cout<<"["<<ss<<","<<se<<"] = "<<st[node]<<" now\n";
		if(ss != se)
		{
			lz[node*2+1] += lz[node];
			lz[node*2+2] += lz[node];
		}
		lz[node] = 0;
	}
 
	void upd(int node, int ss, int se, int l, int r, ldd val)
	{
		push(node, ss, se);
		if(ss > r or se < l)
			return;
		if(ss >= l and se <= r)
		{
			lz[node] += val;
			// cout<<"added "<<val<<" to the entire range ["<<ss<<","<<se<<"] \n";
			push(node, ss, se);
			return;
		}
		int mid = (ss + se)/2;
		upd(node*2+1, ss, mid, l, r, val);
		upd(node*2+2, mid + 1, se, l, r, val);
		st[node] = max(st[node*2+1], st[node*2+2]);
		// cout<<"updated ["<<ss<<','<< se<<"] to "<<st[node]<<'\n';
	}
 
	int quer(int node, int ss, int se)
	{
		// cout<<"Asking ["<<ss<<' '<<se<<"] -> "<<st[node]<<'\n';
		// push(node, ss, se);
		if(ss == se)
			return ss;
		int mid = (ss + se)/2;
		push(node*2+1, ss, mid);
		if(st[node*2+1] == st[node])
			return quer(node*2+1, ss, mid);
		push(node*2+2,mid +1, se);
		return quer(node*2+2, mid + 1, se);
	}
 
	Segtree_main()
	{
		F0R(i, 4*MAXN)
			st[i] = lz[i] = 0;
	}
 
	inline void update(int l, int r, ldd val)
	{
		// cout<<"asked for update("<<l<<','<<r<<','<<val<<")\n";
		upd(0, 0, MAXN, l, r, val);
	}
 
	inline int query()
	{
		push(0, 0, MAXN); 
		int i = quer(0, 0, MAXN);
		// cout<<"index found is "<<i<<'\n';
		ll p = aux.query(i) * y[i];
      	p %= MOD;
		return p;
	}
 
} S;
 
 
 
int updateX(int pos, int val)
{
	aux.update(pos, (ll)val);
	S.update(pos, MAXN, log2(val) - log2(x[pos]));
	x[pos] = val;
	return S.query();
}
 
int updateY(int pos, int val)
{
	// aux.update(pos, val);
	S.update(pos, pos, log2(val) - log2(y[pos]));
	y[pos] = val;
	return S.query();
}
 
int init(int N, int* X, int* Y)
{
	ll amt = 0, prod = 1; 
	F0R(i, N)
	{
		x[i] = X[i];
		y[i] = Y[i];
		S.update(i, MAXN, log2(x[i]));
		S.update(i, i, log2(y[i]));
		aux.update(i, X[i]);
		prod *= X[i];
		amt = max(amt, prod*Y[i]);
	}
	return updateX(0, x[0]);
}
/*
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
 
	int N, X[120], Y[120], M, j, i, k;
	cin>>N;
	FOR(i, N)
		cin>>X[i];
	FOR(i, N)	
		cin>>Y[i];
	cout<<init(N, X, Y)<<endl;
	cin>>M;
	FOR(i, M)
	{
		char c;
		cin>>c>>j>>k;
		if(c == 'X')
			cout<<updateX(j, k)<<endl;
		else
			cout<<updateY(j, k)<<endl;
	}
	return 0;
}*/

Compilation message

horses.cpp: In member function 'int Segtree_main::query()':
horses.cpp:162:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return p;
          ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78584 KB Output is correct
2 Correct 70 ms 78652 KB Output is correct
3 Correct 70 ms 78584 KB Output is correct
4 Correct 66 ms 78584 KB Output is correct
5 Correct 68 ms 78584 KB Output is correct
6 Correct 67 ms 78584 KB Output is correct
7 Correct 67 ms 78560 KB Output is correct
8 Correct 67 ms 78584 KB Output is correct
9 Correct 67 ms 78712 KB Output is correct
10 Correct 66 ms 78584 KB Output is correct
11 Correct 67 ms 78584 KB Output is correct
12 Correct 66 ms 78584 KB Output is correct
13 Correct 67 ms 78588 KB Output is correct
14 Correct 68 ms 78584 KB Output is correct
15 Correct 67 ms 78584 KB Output is correct
16 Correct 71 ms 78584 KB Output is correct
17 Correct 68 ms 78584 KB Output is correct
18 Correct 67 ms 78584 KB Output is correct
19 Correct 66 ms 78584 KB Output is correct
20 Correct 68 ms 78584 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78584 KB Output is correct
2 Correct 66 ms 78584 KB Output is correct
3 Correct 67 ms 78584 KB Output is correct
4 Correct 69 ms 78632 KB Output is correct
5 Correct 68 ms 78616 KB Output is correct
6 Correct 67 ms 78712 KB Output is correct
7 Correct 66 ms 78584 KB Output is correct
8 Correct 68 ms 78584 KB Output is correct
9 Correct 67 ms 78584 KB Output is correct
10 Correct 66 ms 78584 KB Output is correct
11 Correct 67 ms 78584 KB Output is correct
12 Correct 67 ms 78584 KB Output is correct
13 Correct 67 ms 78736 KB Output is correct
14 Correct 67 ms 78584 KB Output is correct
15 Correct 68 ms 78588 KB Output is correct
16 Correct 66 ms 78584 KB Output is correct
17 Correct 67 ms 78584 KB Output is correct
18 Correct 67 ms 78584 KB Output is correct
19 Correct 67 ms 78584 KB Output is correct
20 Correct 67 ms 78584 KB Output is correct
21 Correct 66 ms 78712 KB Output is correct
22 Correct 67 ms 78584 KB Output is correct
23 Correct 69 ms 78584 KB Output is correct
24 Correct 70 ms 78712 KB Output is correct
25 Correct 70 ms 78712 KB Output is correct
26 Correct 71 ms 78712 KB Output is correct
27 Correct 70 ms 78712 KB Output is correct
28 Correct 71 ms 78712 KB Output is correct
29 Correct 69 ms 78712 KB Output is correct
30 Correct 70 ms 78712 KB Output is correct
31 Correct 68 ms 78584 KB Output is correct
32 Correct 69 ms 78584 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 91040 KB Output is correct
2 Correct 1020 ms 90864 KB Output is correct
3 Correct 969 ms 91008 KB Output is correct
4 Correct 1022 ms 90984 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78584 KB Output is correct
2 Correct 67 ms 78584 KB Output is correct
3 Correct 69 ms 78584 KB Output is correct
4 Correct 67 ms 78584 KB Output is correct
5 Correct 68 ms 78584 KB Output is correct
6 Correct 67 ms 78584 KB Output is correct
7 Correct 67 ms 78584 KB Output is correct
8 Correct 67 ms 78584 KB Output is correct
9 Correct 68 ms 78584 KB Output is correct
10 Correct 66 ms 78584 KB Output is correct
11 Correct 66 ms 78712 KB Output is correct
12 Correct 67 ms 78584 KB Output is correct
13 Correct 67 ms 78588 KB Output is correct
14 Correct 66 ms 78584 KB Output is correct
15 Correct 68 ms 78584 KB Output is correct
16 Correct 66 ms 78600 KB Output is correct
17 Correct 67 ms 78584 KB Output is correct
18 Correct 66 ms 78564 KB Output is correct
19 Correct 67 ms 78584 KB Output is correct
20 Correct 67 ms 78584 KB Output is correct
21 Correct 67 ms 78584 KB Output is correct
22 Correct 67 ms 78592 KB Output is correct
23 Correct 69 ms 78584 KB Output is correct
24 Correct 70 ms 78712 KB Output is correct
25 Correct 70 ms 78712 KB Output is correct
26 Correct 70 ms 78712 KB Output is correct
27 Correct 69 ms 78712 KB Output is correct
28 Correct 69 ms 78584 KB Output is correct
29 Correct 70 ms 78584 KB Output is correct
30 Correct 70 ms 78584 KB Output is correct
31 Correct 70 ms 78584 KB Output is correct
32 Correct 69 ms 78584 KB Output is correct
33 Correct 682 ms 90232 KB Output is correct
34 Correct 656 ms 90232 KB Output is correct
35 Incorrect 752 ms 90044 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78584 KB Output is correct
2 Correct 68 ms 78584 KB Output is correct
3 Correct 66 ms 78584 KB Output is correct
4 Correct 74 ms 78584 KB Output is correct
5 Correct 67 ms 78584 KB Output is correct
6 Correct 67 ms 78584 KB Output is correct
7 Correct 67 ms 78584 KB Output is correct
8 Correct 67 ms 78588 KB Output is correct
9 Correct 68 ms 78584 KB Output is correct
10 Correct 67 ms 78584 KB Output is correct
11 Correct 68 ms 78584 KB Output is correct
12 Correct 68 ms 78584 KB Output is correct
13 Correct 68 ms 78552 KB Output is correct
14 Correct 68 ms 78584 KB Output is correct
15 Correct 67 ms 78584 KB Output is correct
16 Correct 66 ms 78584 KB Output is correct
17 Correct 67 ms 78584 KB Output is correct
18 Correct 66 ms 78612 KB Output is correct
19 Correct 68 ms 78584 KB Output is correct
20 Correct 67 ms 78584 KB Output is correct
21 Correct 67 ms 78716 KB Output is correct
22 Correct 67 ms 78584 KB Output is correct
23 Correct 71 ms 78584 KB Output is correct
24 Correct 70 ms 78588 KB Output is correct
25 Correct 69 ms 78716 KB Output is correct
26 Correct 72 ms 78712 KB Output is correct
27 Correct 69 ms 78584 KB Output is correct
28 Correct 70 ms 78588 KB Output is correct
29 Correct 69 ms 78584 KB Output is correct
30 Correct 69 ms 78712 KB Output is correct
31 Correct 69 ms 78584 KB Output is correct
32 Correct 69 ms 78584 KB Output is correct
33 Correct 763 ms 90960 KB Output is correct
34 Correct 1033 ms 90828 KB Output is correct
35 Correct 959 ms 91000 KB Output is correct
36 Correct 1025 ms 90872 KB Output is correct
37 Correct 683 ms 89976 KB Output is correct
38 Correct 658 ms 89976 KB Output is correct
39 Incorrect 754 ms 89848 KB Output isn't correct
40 Halted 0 ms 0 KB -