Submission #955656

#	Time	Username	Problem	Language	Result	Execution time	Memory
955656		emad234	Horses (IOI15_horses)	C++17	20 / 100	172 ms	58372 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 5e5 + 5;
using namespace std;
int NN;
struct tree{
	vector<pii>seg;
	ll s,e;
	void init(int n){
		NN = exp2(ceil(log2(n)));
		seg.resize(NN * 4);
	}
	ll queryMax(int l = 1,int r = NN,int ind = 1){
		if(l > e || r < s) return 0;
		if(l >= s && r <= e) return seg[ind].F;
		int md = (l + r) / 2;
		return max(queryMax(l,md,ind * 2),queryMax(md + 1,r,ind * 2 + 1));
	}
	ll queryProd(int l = 1, int r = NN, int ind = 1)
	{
		if (l > e || r < s)
			return 1;
		if (l >= s && r <= e)
			return seg[ind].S;
		int md = (l + r) / 2;
		return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod;
	}
	void update(pii val,int ind){
		ind += NN;
		seg[ind] = val;
		while(ind /= 2){
			seg[ind].F = max(seg[ind * 2].F,seg[ind * 2 + 1].F);
			seg[ind].S  = (seg[ind * 2].S * seg[ind * 2 + 1].S) % mod;
		}
	}
} seg;
struct ones{
	ll l,r;
	friend bool operator<(ones a, ones b){
		return a.l < b.l;
	}
};
set<ones>s;
ll x[mxN],y[mxN];
int n;
ll solve(){
	int st,id = 0;
	int i = n - 1;
	while(i && id <= 100){
		if(x[i] == 1){
			auto it = s.upper_bound({i,i});
			it--;
			i = (*it).l;
		}
		i--;
		id++;
	}
	ll mx = -1,mxid = -1;
	int prd = 1;
	for(i;i < n;i++){
		if(x[i] == 1){
			auto it = s.lower_bound({i,i});
			seg.s = (*it).l + 1, seg.e = (*it).r + 1;
			int val = seg.queryMax();
			if(val * prd > mx){
				mx = val;
				mxid = i;
				prd = 1;
			}
			i = (*it).r;
			continue;
		}
		if(prd * x[i] > mx){
			mx = y[i];
			mxid = i;
			prd = 1;
			continue;
		}
		prd *= x[i];
		if(prd * y[i] > mx){
			mx = y[i];
			mxid = i;
			prd = 1;
			continue;
		}
	}
	seg.s = 1;seg.e = mxid + 1;
	return (mx * seg.queryProd()) % mod; 
}
int init(int N, int X[], int Y[]) {
	seg.init(N);
	n = N;
	for(int i = 0;i < N;i++){
		y[i] = Y[i];
		x[i] = X[i];
		seg.update({Y[i],X[i]},i);
	}
	int l = -1,r = -1;
	for(int i = 0;i < N;i++){
		if(X[i] == 1){
			if(l == -1) l = i;
			r = i;
		}else{
			if(l != -1){
				s.insert({l,r});
				l = r = -1;
			}
		}
	}
	if (l != -1)
	{
		s.insert({l, r});
		l = r = -1;
	}
	return solve();
}

int updateX(int pos, int val) {	
	if(x[pos] != 1 && val == 1){
		auto it = s.upper_bound({pos,pos});
		int l = pos,r = pos;
		if(it != s.end() && (*it).l == pos + 1){
			l = pos,r = (*it).r;
			s.erase(it);
			s.insert({l,r});
		}else s.insert({pos,pos});
		it = s.lower_bound({pos,pos});
		auto p = s.lower_bound({l,r});
		if(it != s.begin()){
			it--;
			if((*it).r == l - 1){
				l = (*it).l;
				s.erase(it);
				s.erase(s.lower_bound({pos,pos}));
				s.insert({l,r});
			}
		}
	}
	if(x[pos] == 1 && val != 1){
		auto it = s.upper_bound({pos,0});
		it--;
		int l = (*it).l,r = pos - 1,l1 = pos + 1,r1 = (*it).r;
		s.erase(it);
		if(l <= r) s.insert({l,r});
		if(l1 <= r1) s.insert({l1,r1});
	}
	x[pos] = val;
	seg.update({y[pos], x[pos]},pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	seg.update({y[pos], x[pos]}, pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In member function 'void tree::init(int)':
horses.cpp:15:12: warning: conversion from 'double' to 'int' may change value [-Wfloat-conversion]
   15 |   NN = exp2(ceil(log2(n)));
      |        ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:58:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   58 |    i = (*it).l;
      |        ~~~~~~^
horses.cpp:65:6: warning: statement has no effect [-Wunused-value]
   65 |  for(i;i < n;i++){
      |      ^
horses.cpp:69:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |    int val = seg.queryMax();
      |              ~~~~~~~~~~~~^~
horses.cpp:75:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |    i = (*it).r;
      |        ~~~~~~^
horses.cpp:84:7: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |   prd *= x[i];
      |   ~~~~^~~~~~~
horses.cpp:52:6: warning: unused variable 'st' [-Wunused-variable]
   52 |  int st,id = 0;
      |      ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:120:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:128:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |    l = pos,r = (*it).r;
      |                ~~~~~~^
horses.cpp:137:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  137 |     l = (*it).l;
      |         ~~~~~~^
horses.cpp:133:8: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  133 |   auto p = s.lower_bound({l,r});
      |        ^
horses.cpp:147:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |   int l = (*it).l,r = pos - 1,l1 = pos + 1,r1 = (*it).r;
      |           ~~~~~~^
horses.cpp:147:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |   int l = (*it).l,r = pos - 1,l1 = pos + 1,r1 = (*it).r;
      |                                                 ~~~~~~^
horses.cpp:154:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  154 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:160:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |  return solve();
      |         ~~~~~^~

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