oj.uz

Submission #798726

# Submission time Handle Problem Language Result Execution time Memory
798726 2023-07-31T02:09:30 Z Username4132 Horses (IOI15_horses) C++14
17 / 100
 229 ms 44344 KB 
#include "horses.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second


struct node{
	int pr;
	pii mx;
	node(int _pr=0, pii _mx={0, 0}) : pr(_pr), mx(_mx) {}
};

const int MAXN = 500010, MOD = 1000000007;
int n;
node tr[2*MAXN];
set<int> ones;

node combine(node a, node b){
	return node((a.pr*((ll)b.pr))%MOD, max(a.mx, b.mx));
}

void update(int p, node value){
	p+=n;
	tr[p]=value;
	while(p>1) p>>=1, tr[p]=combine(tr[p<<1], tr[p<<1|1]);
}
 
node query(int l, int r){
	node ret = node(1, {0, -1});
	for(l+=n, r+=n; l<r; l>>=1, r>>=1){
		if(l&1) ret = combine(ret, tr[l++]);
		if(r&1) ret = combine(ret, tr[--r]);
	}
	return ret;
} 
 
int solve(){
	ll prod=1;
	vector<int> lis;
	int sz = ones.size();
 
	auto itr = ones.end();
	forn(i, sz){
		itr = prev(itr);
		prod*=tr[n + *itr].pr;
		lis.PB(*itr);
		if(prod>1000000010) break;
	}
	reverse(lis.begin(), lis.end());
 
	pli basic = query(0, n).mx;
	if(lis.empty()) return basic.F;

	ll p=1;
	pli mx={-1, -1};
	for(int el:lis){
		if(el!=lis.front()) p*=tr[n + el].pr;
		pli opt = query(el, n).mx;
		opt.F*=p;
		mx = max(mx, opt);
	}
	if(mx.F > (basic.F / tr[n + lis.front()].pr)) return (tr[n+mx.S].mx.F*((ll)query(0, mx.S + 1).pr));
	else return basic.F;
}
 
int init(int N, int X[], int Y[]) {
	n=N;
	forn(i, n){
		tr[n+i]=node(X[i], {Y[i], i});
		if(tr[n+i].pr!=1) ones.insert(i);
	}
	dforsn(i, 1, n) tr[i]=combine(tr[i<<1], tr[i<<1|1]);
	return solve();
}
 
int updateX(int pos, int val) {	
	if(tr[n+pos].pr==1 && val!=1) ones.insert(pos);
	if(tr[n+pos].pr!=1 && val==1) ones.erase(pos);
	update(pos, node(val, tr[n+pos].mx));
	return solve();
}
 
int updateY(int pos, int val) {
	update(pos, node(tr[n+pos].pr, {val, pos}));
	return solve();
}

Compilation message

horses.cpp: In function 'node combine(node, node)':
horses.cpp:31:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   31 |  return node((a.pr*((ll)b.pr))%MOD, max(a.mx, b.mx));
      |              ~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int solve()':
horses.cpp:52:20: warning: conversion from 'std::set<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   52 |  int sz = ones.size();
      |           ~~~~~~~~~^~
horses.cpp:15:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define F first
      |           ^
horses.cpp:64:31: note: in expansion of macro 'F'
   64 |  if(lis.empty()) return basic.F;
      |                               ^
horses.cpp:15:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define F first
      |           ^
horses.cpp:75:20: note: in expansion of macro 'F'
   75 |  else return basic.F;
      |                    ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12004 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 12040 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 6 ms 11972 KB Output is correct
10 Correct 6 ms 11996 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 5 ms 11936 KB Output is correct
13 Correct 5 ms 11972 KB Output is correct
14 Correct 5 ms 12040 KB Output is correct
15 Correct 5 ms 12048 KB Output is correct
16 Correct 5 ms 11988 KB Output is correct
17 Correct 5 ms 12048 KB Output is correct
18 Correct 5 ms 11988 KB Output is correct
19 Correct 5 ms 12048 KB Output is correct
20 Correct 5 ms 11988 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12036 KB Output is correct
2 Correct 6 ms 12036 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11932 KB Output is correct
7 Correct 6 ms 12032 KB Output is correct
8 Correct 6 ms 12048 KB Output is correct
9 Correct 6 ms 12048 KB Output is correct
10 Correct 5 ms 12032 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 5 ms 11988 KB Output is correct
13 Correct 5 ms 11988 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 5 ms 11944 KB Output is correct
16 Correct 5 ms 11988 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 6 ms 11988 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 5 ms 11988 KB Output is correct
21 Incorrect 5 ms 11988 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 5 ms 12012 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 5 ms 11936 KB Output is correct
10 Correct 5 ms 11988 KB Output is correct
11 Correct 5 ms 12040 KB Output is correct
12 Correct 5 ms 11988 KB Output is correct
13 Correct 6 ms 12040 KB Output is correct
14 Correct 5 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 5 ms 12048 KB Output is correct
17 Correct 5 ms 12044 KB Output is correct
18 Correct 5 ms 11988 KB Output is correct
19 Correct 5 ms 11988 KB Output is correct
20 Correct 7 ms 12120 KB Output is correct
21 Incorrect 6 ms 12048 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 5 ms 11992 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Correct 5 ms 11988 KB Output is correct
7 Correct 5 ms 12040 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 5 ms 12048 KB Output is correct
10 Correct 5 ms 12044 KB Output is correct
11 Correct 5 ms 12000 KB Output is correct
12 Correct 5 ms 12044 KB Output is correct
13 Correct 5 ms 11988 KB Output is correct
14 Correct 5 ms 11988 KB Output is correct
15 Correct 5 ms 11988 KB Output is correct
16 Correct 5 ms 11988 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 5 ms 11988 KB Output is correct
19 Correct 5 ms 12044 KB Output is correct
20 Correct 5 ms 12044 KB Output is correct
21 Incorrect 5 ms 11988 KB Output isn't correct
22 Halted 0 ms 0 KB -