oj.uz

Submission #832528

# Submission time Handle Problem Language Result Execution time Memory
832528 2023-08-21T11:11:52 Z aymanrs Horses (IOI15_horses) C++14
0 / 100
 358 ms 40516 KB 
#include<bits/stdc++.h>
#define L(i) (i<<1)
#define R(i) (i<<1|1)
const int MOD = 1e9+7;
using namespace std;
long long binp(long long a, int n){
	int r = 1;
	while(n){
		if(n&1) r = a*r%MOD;
		a = a*a%MOD;
		n>>=1;
	}
	return r;
}
set<int> s;
vector<int> x, y;
const int nx = 5e5+10;
int st[4*nx], ind;
long long BIT[nx+1];
int que(int i){
	int ans = y[i-1];
	while(i){
		ans = (BIT[i]*ans)%MOD;
		i -= i&-i;
	}
	return ans;
}
void up(int i, int n, int v){
	while(i <= n){
		BIT[i] = BIT[i]*v%MOD;
		i += i&-i;
	}
}
void cons(int i, int l, int r){
	if(l==r){
		st[i] = l;
		return;
	}	
	int mid = l+r>>1;
	cons(L(i), l, mid);
	cons(R(i), mid+1, r);
	auto p = s.lower_bound(st[L(i)]+1);
	long long f = y[st[R(i)]];
	while(p!=s.end() && *p <= st[R(i)] && f < y[st[L(i)]]){
		f *= x[*p];
		p++;
	}
	if(f <= y[st[L(i)]]) st[i] = st[L(i)];
	else st[i] = st[R(i)];
}
void upd(int i, int l, int r){
	if(l==r) return;
	int mid = l+r>>1;
	if(ind > mid) upd(R(i), mid+1, r);
	else upd(L(i),l,mid);
	auto p = s.lower_bound(st[L(i)]+1);
	long long f = y[st[R(i)]];
	while(p!=s.end() && *p <= st[R(i)] && f <= y[st[L(i)]]){
		f *= x[*p];
		p++;
	}
	if(f <= y[st[L(i)]]) st[i] = st[L(i)];
	else st[i] = st[R(i)];
}
int init(int N, int X[], int Y[]){
	fill(BIT, BIT+N+1, 1);
	for(int i = 0;i < N;i++){
		x.push_back(X[i]);
		y.push_back(Y[i]);
		if(X[i] > 1) {
			s.insert(i);
			up(i+1, N, X[i]);
		}
	}
	cons(1, 0, N-1);
	return que(st[1]+1);
}
int updateX(int pos, int val){
	up(pos+1, x.size(), val*binp(x[pos], MOD-2)%MOD);
	if((val > 1) ^ (x[pos] > 1)){
		if(x[pos] > 1) s.erase(pos);
		else s.insert(pos);
	}
	x[pos] = val;
	ind = pos;
	upd(1, 0, x.size()-1);
	return que(st[1]+1);
}
int updateY(int pos, int val){
	y[pos] = val;
	ind = pos;
	upd(1, 0, x.size()-1);
	return que(st[1]+1);
}

Compilation message

horses.cpp: In function 'long long int binp(long long int, int)':
horses.cpp:9:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    9 |   if(n&1) r = a*r%MOD;
      |               ~~~^~~~
horses.cpp: In function 'int que(int)':
horses.cpp:23:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   23 |   ans = (BIT[i]*ans)%MOD;
      |         ~~~~~~~~~~~~^~~~
horses.cpp: In function 'void cons(int, int, int)':
horses.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid = l+r>>1;
      |            ~^~
horses.cpp: In function 'void upd(int, int, int)':
horses.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid = l+r>>1;
      |            ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:79:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |  up(pos+1, x.size(), val*binp(x[pos], MOD-2)%MOD);
      |            ~~~~~~^~
horses.cpp:79:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  up(pos+1, x.size(), val*binp(x[pos], MOD-2)%MOD);
      |                      ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:86:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   86 |  upd(1, 0, x.size()-1);
      |            ~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:92:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   92 |  upd(1, 0, x.size()-1);
      |            ~~~~~~~~^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -