oj.uz

Submission #1030271

# Submission time Handle Problem Language Result Execution time Memory
1030271 2024-07-22T01:52:07 Z pcc Horses (IOI15_horses) C++17
34 / 100
 1500 ms 24944 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const ll mod = 1e9+7;
const ll mxn = 5e5+10;

ll pref[mxn];
ll N;
ll arr[mxn],brr[mxn];
set<int> st;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	ll seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			seg[now] = arr[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
		return;
	}
	void modify(int now,int l,int r,int p,ll v){
		if(l == r){
			seg[now] = v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else{
			auto re = getval(ls,l,mid,s,e)*getval(rs,mid+1,r,s,e);
			if(re>=mod)return mod+re%mod;
			else return re;
		}
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;

bool cmp(int a,int b){
	if(a>b)return brr[a]*seg.getval(0,0,N-1,b+1,a)<brr[b];
	else return brr[a]<brr[b]*seg.getval(0,0,N-1,a+1,b);
}

ll getans(){
	vector<int> v(N);
	iota(v.begin(),v.end(),0);
	sort(v.begin(),v.end(),cmp);
	return seg.getval(0,0,N-1,0,v.back())*brr[v.back()]%mod;
}

int init(int NN, int X[], int Y[]) {
	N = NN;
	for(int i = 0;i<N;i++){
		arr[i] = X[i];
		brr[i] = Y[i];
	}
	seg.build(0,0,N-1);
	return getans();
}

int updateX(int pos, int val) {	
	seg.modify(0,0,N-1,pos,arr[pos]=val);
	return getans();
}

int updateY(int pos, int val) {
	brr[pos] = val;
	return getans();
}

Compilation message

horses.cpp: In function 'bool cmp(int, int)':
horses.cpp:61:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |  if(a>b)return brr[a]*seg.getval(0,0,N-1,b+1,a)<brr[b];
      |                                      ~^~
horses.cpp:62:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |  else return brr[a]<brr[b]*seg.getval(0,0,N-1,a+1,b);
      |                                           ~^~
horses.cpp: In function 'long long int getans()':
horses.cpp:69:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |  return seg.getval(0,0,N-1,0,v.back())*brr[v.back()]%mod;
      |                        ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:78:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |  seg.build(0,0,N-1);
      |                ~^~
horses.cpp:79:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:83:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  seg.modify(0,0,N-1,pos,arr[pos]=val);
      |                 ~^~
horses.cpp:84:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return getans();
      |         ~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 633 ms 6608 KB Output is correct
24 Correct 602 ms 6488 KB Output is correct
25 Correct 526 ms 6488 KB Output is correct
26 Correct 528 ms 6612 KB Output is correct
27 Correct 537 ms 6488 KB Output is correct
28 Correct 465 ms 6492 KB Output is correct
29 Correct 405 ms 6740 KB Output is correct
30 Correct 468 ms 6608 KB Output is correct
31 Correct 423 ms 6488 KB Output is correct
32 Correct 390 ms 6860 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 24924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6596 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 590 ms 6612 KB Output is correct
24 Correct 534 ms 6604 KB Output is correct
25 Correct 518 ms 6492 KB Output is correct
26 Correct 540 ms 6612 KB Output is correct
27 Correct 527 ms 6492 KB Output is correct
28 Correct 483 ms 6608 KB Output is correct
29 Correct 387 ms 6488 KB Output is correct
30 Correct 515 ms 6620 KB Output is correct
31 Correct 451 ms 6488 KB Output is correct
32 Correct 395 ms 348 KB Output is correct
33 Execution timed out 1532 ms 22356 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 655 ms 6608 KB Output is correct
24 Correct 603 ms 6608 KB Output is correct
25 Correct 580 ms 6608 KB Output is correct
26 Correct 567 ms 6616 KB Output is correct
27 Correct 608 ms 6620 KB Output is correct
28 Correct 516 ms 6616 KB Output is correct
29 Correct 429 ms 6648 KB Output is correct
30 Correct 503 ms 6612 KB Output is correct
31 Correct 427 ms 6608 KB Output is correct
32 Correct 440 ms 6492 KB Output is correct
33 Execution timed out 1562 ms 24944 KB Time limit exceeded
34 Halted 0 ms 0 KB -