Submission #167535

#	Time	Username	Problem	Language	Result	Execution time	Memory
167535		itgl	Simple game (IZhO17_game)	C++14	0 / 100	22 ms	9848 KiB

game

#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 (stderr)

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())
           ~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51