oj.uz

Submission #773154

# Submission time Handle Problem Language Result Execution time Memory
773154 2023-07-04T15:50:12 Z 1ne Horses (IOI15_horses) C++14
17 / 100
 63 ms 80176 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long>cur;
const int mod = 1e9 + 7;
long long inf = 1e9 + 1;
vector<long long>x,y;
int n;
int valid = -1;
long long ans = 0;
struct dataa{
	long long vx,vy,ans =0;
	void add(long long left,long long right,long long val,int op){
		if (op == 1){
			vx = val;
		} 
		else{
			vy = val;
		}
		ans = vx * vy;
		//sum += val *(right - left + 1);
	}
};
long long power(long long a,long long b){
        
     long long result =1;
       while(b>0){
         if(b&1)result=(result*a)%mod; //if you want you can add mod here!
          a=(a*a)%mod; //here also.
          b>>=1;// shifted one bit similar to divide by 2 :)
      }
 return result;}
 //if m is prime then a^n = a^(n%(mod-1));
struct Segment_Tree{
	vector<dataa>tree;
	void build(long long node,long long left,long long right,vector<long long>&arr,vector<long long>&brr,long long n){
		if (left == right){
			tree[node].vx = arr[left];
			tree[node].vy = brr[left];
			tree[node].ans = min(inf,arr[left] * brr[left]);
			return ;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		build(node + 1,left,mid,arr,brr,n);
		build(z,mid + 1,right,arr,brr,n);
		tree[node] = combine(tree[node + 1],tree[z]);
	}
	void init(long long n,vector<long long>&arr,vector<long long>&brr){
		tree.resize(2*n - 1);
		build(0,0,n-1,arr,brr,n);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		res.vx = min(left.vx * right.vx,inf);
		res.vy = right.vy;
		res.ans = max(left.ans,min(left.vx * right.ans,inf));
		return res;
	}
	dataa query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return {0,0,0};
		if (qleft<=left && qright>=right){
			return tree[node];
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long v,int op){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			tree[node].add(left,right,v,op);
			return;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,v,op);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,v,op);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};
Segment_Tree st;	
int init(int N, int X[], int Y[]) {
	cur.resize(N);
	n = N;
	for (int i = 0;i<n;++i){
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	st.init(n,x,y);
	long long v = 1;
	for (int i = 0;i<N;++i){
		bool ok = true;
		long long u = 1;
		for (int j = i + 1;j<N;++j){
			if (u * y[j] * x[j] > y[i]){
				ok = false;
				break;
			}
			u*=x[j];		
		}
		v = (v * x[i])%mod;
		if (ok){
			valid = i;
			return ans=(v * y[i])%mod;
		}
	}	
}

int updateX(int pos, int val) {	
	if (pos <= valid){
		ans = ((ans * power(x[pos],mod - 2))%mod * val)%mod;
		x[pos] = val;		
	}
	else if (x[pos] >= val){
		x[pos] = val;	
	}
	else{
		ans = ((ans * power(y[valid],mod - 2))%mod);
		st.update(0,0,n - 1,pos,pos,val,1);
		x[pos] = val;
		while(valid < n - 1 && st.query(0,0,n - 1,valid + 1,n - 1).ans > y[valid]){
			++valid;
			ans = (ans * x[valid])%mod;
		}
		ans = (ans * y[valid])%mod;	
	}
	return ans;
}

int updateY(int pos, int val) {
	
}

Compilation message

horses.cpp: In member function 'void dataa::add(long long int, long long int, long long int, int)':
horses.cpp:13:21: warning: unused parameter 'left' [-Wunused-parameter]
   13 |  void add(long long left,long long right,long long val,int op){
      |           ~~~~~~~~~~^~~~
horses.cpp:13:36: warning: unused parameter 'right' [-Wunused-parameter]
   13 |  void add(long long left,long long right,long long val,int op){
      |                          ~~~~~~~~~~^~~~~
horses.cpp: In member function 'void Segment_Tree::build(long long int, long long int, long long int, std::vector<long long int>&, std::vector<long long int>&, long long int)':
horses.cpp:36:113: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   36 |  void build(long long node,long long left,long long right,vector<long long>&arr,vector<long long>&brr,long long n){
      |                                                                                                       ~~~~~~~~~~^
horses.cpp:8:5: note: shadowed declaration is here
    8 | int n;
      |     ^
horses.cpp: In member function 'void Segment_Tree::init(long long int, std::vector<long long int>&, std::vector<long long int>&)':
horses.cpp:49:22: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   49 |  void init(long long n,vector<long long>&arr,vector<long long>&brr){
      |            ~~~~~~~~~~^
horses.cpp:8:5: note: shadowed declaration is here
    8 | int n;
      |     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:109:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |    return ans=(v * y[i])%mod;
      |           ~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:132:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:137:1: warning: no return statement in function returning non-void [-Wreturn-type]
  137 | }
      | ^
horses.cpp:135:17: warning: unused parameter 'pos' [-Wunused-parameter]
  135 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:135:26: warning: unused parameter 'val' [-Wunused-parameter]
  135 | int updateY(int pos, int val) {
      |                      ~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:112:1: warning: control reaches end of non-void function [-Wreturn-type]
  112 | }
      | ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 244 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 412 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 2 ms 468 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 80176 KB Execution killed with signal 11
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 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 276 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 2 ms 468 KB Execution killed with signal 11
22 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 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 2 ms 468 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -