oj.uz

Submission #235100

# Submission time Handle Problem Language Result Execution time Memory
235100 2020-05-27T05:10:44 Z anubhavdhar Horses (IOI15_horses) C++14
54 / 100
 1043 ms 100088 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
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:161: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 76 ms 78584 KB Output is correct
2 Correct 69 ms 78584 KB Output is correct
3 Correct 67 ms 78584 KB Output is correct
4 Correct 66 ms 78584 KB Output is correct
5 Correct 66 ms 78584 KB Output is correct
6 Correct 66 ms 78584 KB Output is correct
7 Correct 67 ms 78584 KB Output is correct
8 Correct 66 ms 78584 KB Output is correct
9 Correct 66 ms 78584 KB Output is correct
10 Correct 68 ms 78584 KB Output is correct
11 Correct 67 ms 78712 KB Output is correct
12 Correct 67 ms 78584 KB Output is correct
13 Correct 67 ms 78584 KB Output is correct
14 Correct 65 ms 78588 KB Output is correct
15 Correct 66 ms 78584 KB Output is correct
16 Correct 66 ms 78584 KB Output is correct
17 Correct 66 ms 78584 KB Output is correct
18 Correct 66 ms 78584 KB Output is correct
19 Correct 66 ms 78456 KB Output is correct
20 Correct 66 ms 78584 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 78712 KB Output is correct
2 Correct 66 ms 78584 KB Output is correct
3 Correct 65 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 66 ms 78584 KB Output is correct
8 Correct 66 ms 78584 KB Output is correct
9 Correct 66 ms 78584 KB Output is correct
10 Correct 67 ms 78584 KB Output is correct
11 Correct 66 ms 78584 KB Output is correct
12 Correct 65 ms 78584 KB Output is correct
13 Correct 68 ms 78584 KB Output is correct
14 Correct 66 ms 78584 KB Output is correct
15 Correct 66 ms 78584 KB Output is correct
16 Correct 67 ms 78584 KB Output is correct
17 Correct 66 ms 78584 KB Output is correct
18 Correct 66 ms 78584 KB Output is correct
19 Correct 65 ms 78584 KB Output is correct
20 Correct 66 ms 78584 KB Output is correct
21 Correct 66 ms 78584 KB Output is correct
22 Correct 70 ms 78584 KB Output is correct
23 Correct 68 ms 78616 KB Output is correct
24 Correct 69 ms 78712 KB Output is correct
25 Correct 70 ms 78712 KB Output is correct
26 Correct 69 ms 78712 KB Output is correct
27 Correct 68 ms 78712 KB Output is correct
28 Correct 70 ms 78712 KB Output is correct
29 Correct 68 ms 78584 KB Output is correct
30 Correct 69 ms 78712 KB Output is correct
31 Correct 68 ms 78716 KB Output is correct
32 Correct 68 ms 78712 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 91352 KB Output is correct
2 Correct 1031 ms 100088 KB Output is correct
3 Correct 994 ms 91252 KB Output is correct
4 Correct 1042 ms 95156 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78584 KB Output is correct
2 Correct 67 ms 78712 KB Output is correct
3 Correct 67 ms 78584 KB Output is correct
4 Correct 67 ms 78584 KB Output is correct
5 Correct 66 ms 78584 KB Output is correct
6 Correct 66 ms 78584 KB Output is correct
7 Correct 66 ms 78584 KB Output is correct
8 Correct 67 ms 78584 KB Output is correct
9 Correct 66 ms 78584 KB Output is correct
10 Correct 67 ms 78584 KB Output is correct
11 Correct 67 ms 78588 KB Output is correct
12 Correct 66 ms 78584 KB Output is correct
13 Correct 66 ms 78584 KB Output is correct
14 Correct 66 ms 78584 KB Output is correct
15 Correct 66 ms 78584 KB Output is correct
16 Correct 66 ms 78584 KB Output is correct
17 Correct 66 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 78584 KB Output is correct
22 Correct 71 ms 78584 KB Output is correct
23 Correct 69 ms 78712 KB Output is correct
24 Correct 70 ms 78712 KB Output is correct
25 Correct 69 ms 78716 KB Output is correct
26 Correct 68 ms 78712 KB Output is correct
27 Correct 68 ms 78712 KB Output is correct
28 Correct 68 ms 78712 KB Output is correct
29 Correct 69 ms 78712 KB Output is correct
30 Correct 69 ms 78712 KB Output is correct
31 Correct 68 ms 78712 KB Output is correct
32 Correct 68 ms 78712 KB Output is correct
33 Correct 656 ms 90616 KB Output is correct
34 Correct 655 ms 90488 KB Output is correct
35 Correct 732 ms 97404 KB Output is correct
36 Correct 735 ms 97400 KB Output is correct
37 Correct 604 ms 88696 KB Output is correct
38 Correct 699 ms 89592 KB Output is correct
39 Correct 625 ms 88568 KB Output is correct
40 Correct 725 ms 92408 KB Output is correct
41 Correct 610 ms 88568 KB Output is correct
42 Correct 618 ms 88720 KB Output is correct
43 Correct 691 ms 92792 KB Output is correct
44 Incorrect 695 ms 92892 KB Output isn't correct

Subtask #5
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 67 ms 78584 KB Output is correct
4 Correct 66 ms 78584 KB Output is correct
5 Correct 67 ms 78584 KB Output is correct
6 Correct 66 ms 78584 KB Output is correct
7 Correct 67 ms 78584 KB Output is correct
8 Correct 66 ms 78584 KB Output is correct
9 Correct 67 ms 78588 KB Output is correct
10 Correct 68 ms 78588 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 78584 KB Output is correct
14 Correct 67 ms 78584 KB Output is correct
15 Correct 67 ms 78584 KB Output is correct
16 Correct 67 ms 78712 KB Output is correct
17 Correct 66 ms 78584 KB Output is correct
18 Correct 69 ms 78584 KB Output is correct
19 Correct 71 ms 78584 KB Output is correct
20 Correct 66 ms 78584 KB Output is correct
21 Correct 67 ms 78584 KB Output is correct
22 Correct 68 ms 78584 KB Output is correct
23 Correct 69 ms 78712 KB Output is correct
24 Correct 70 ms 78712 KB Output is correct
25 Correct 69 ms 78712 KB Output is correct
26 Correct 69 ms 78712 KB Output is correct
27 Correct 70 ms 78712 KB Output is correct
28 Correct 72 ms 78632 KB Output is correct
29 Correct 68 ms 78584 KB Output is correct
30 Correct 70 ms 78712 KB Output is correct
31 Correct 71 ms 78840 KB Output is correct
32 Correct 68 ms 78712 KB Output is correct
33 Correct 781 ms 91384 KB Output is correct
34 Correct 1012 ms 100088 KB Output is correct
35 Correct 960 ms 91384 KB Output is correct
36 Correct 1043 ms 95224 KB Output is correct
37 Correct 681 ms 90616 KB Output is correct
38 Correct 666 ms 90624 KB Output is correct
39 Correct 749 ms 97528 KB Output is correct
40 Correct 766 ms 97528 KB Output is correct
41 Correct 608 ms 88696 KB Output is correct
42 Correct 679 ms 89596 KB Output is correct
43 Correct 619 ms 88568 KB Output is correct
44 Correct 700 ms 92536 KB Output is correct
45 Correct 600 ms 88564 KB Output is correct
46 Correct 607 ms 88568 KB Output is correct
47 Correct 697 ms 92936 KB Output is correct
48 Incorrect 716 ms 92920 KB Output isn't correct
49 Halted 0 ms 0 KB -