| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167535 |
2019-12-08T19:37:33 Z |
itgl |
Simple game (IZhO17_game) |
C++14 |
|
22 ms |
9848 KB |
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m;
int a[100005];
vector<int> tree[400005];
void build(int id, int l, int r){
if(l==r){
tree[id].pb(a[l]);
return;
}
build(id*2,l,(l+r)/2);
build(id*2+1,(l+r)/2+1,r);
//merge
int i=0,j=0;
while(i < tree[id * 2].size() && j < tree[id * 2 + 1].size())
{
if(tree[id * 2][i] <= tree[id * 2 + 1][j])
{
tree[id].pb(tree[id * 2][i]);
i++;
}
else {
tree[id].pb(tree[id * 2 + 1][j]);
j++;
}
}
while(i < tree[id * 2].size())
{
tree[id].pb(tree[id * 2][i]);
i++;
}
while(j < tree[id * 2 + 1].size())
{
tree[id].pb(tree[id * 2 + 1][j]);
j++;
}
}
void update(int id, int l, int r, int x, int val){
if(x<l||x>r) return;
if(l==r&&l==x){
tree[id].clear();
tree[id].pb(val);
return;
}
update(id * 2, l, (l + r) / 2, x, val);
update(id * 2 + 1, (l + r) / 2 + 1, r, x, val);
tree[id].clear();
//merge
int i=0,j=0;
while(i < tree[id * 2].size() && j < tree[id * 2 + 1].size())
{
if(tree[id * 2][i] <= tree[id * 2 + 1][j])
{
tree[id].pb(tree[id * 2][i]);
i++;
}
else {
tree[id].pb(tree[id * 2 + 1][j]);
j++;
}
}
while(i < tree[id * 2].size())
{
tree[id].pb(tree[id * 2][i]);
i++;
}
while(j < tree[id * 2 + 1].size())
{
tree[id].pb(tree[id * 2 + 1][j]);
j++;
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
int k;
cin>>k;
if(k==1){
int x, val;
cin>>x>>val;
update(1,1,n,x,val);
}
else{
int m;
cin >> m;
cout<<lower_bound(tree[1].begin(),tree[1].end(),m)-tree[1].begin() << '\n';
}
}
}
Compilation message
game.cpp: In function 'void build(int, int, int)':
game.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < tree[id * 2].size() && j < tree[id * 2 + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:22:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < tree[id * 2].size() && j < tree[id * 2 + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:34:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < tree[id * 2].size())
~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:39:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < tree[id * 2 + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void update(int, int, int, int, int)':
game.cpp:59:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < tree[id * 2].size() && j < tree[id * 2 + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:59:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < tree[id * 2].size() && j < tree[id * 2 + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:71:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < tree[id * 2].size())
~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:76:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < tree[id * 2 + 1].size())
~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9692 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
9848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9692 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
9848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9692 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
9848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
