oj.uz

Submission #38646

# Submission time Handle Problem Language Result Execution time Memory
38646 2018-01-05T10:11:16 Z Ulugbek_Abdimanabov Simple game (IZhO17_game) C++14
0 / 100
 3 ms 10696 KB 
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
#define vi vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define rep(i,a,n) for(ll i=a; i<n; i++)
#define per(i,a,n) for(ll i=n-1; i>=a; i--)
#define F first
#define S second
#define maxx(a,b) a=max(a,b)
#define minn(a,b) a=min(a,b)
#define db(x) cerr << #x << " = " << x << endl
#define N 1111111

using namespace std;

int f[N],a[N];
int n;

void add(int r, int d)
{
                if(r==0)return;
           for(; r<N;)
           {
                f[r]+=d;
               if((r&-r)==r)r*=2;
               else r+=r&-r;
           }
}

int sum(int r)
{
    int ans=0;
    for(; r>0; r-=r&-r)
        ans+=f[r];
    return ans;
}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin>>n;
  int m; cin>>m;

  rep(i,1,n+1)cin>>a[i];

  rep(i,2,n+1)
  {
      add(max(a[i],a[i-1]),1);
      add(min(a[i],a[i-1]),-1);
  }

  while(m--)
  {
      int c,d; cin>>c;
      if(c==1)
      {
          cin>>c>>d;
          if(c>1)
          {
              add(max(a[c],a[c-1]),-1);
              add(min(a[c],a[c-1]),1);
          }
        if(c<n)
         {
            add(max(a[c],a[c+1]),-1);
            add(min(a[c],a[c+1]),1);
         }
         if(d>1)
          {
              add(max(a[d],a[d-1]),1);
              add(min(a[d],a[d-1]),-1);
          }
        if(d<n)
         {
            add(max(a[d],a[d+1]),1);
            add(min(a[d],a[d+1]),-1);
         }

      }
      else
      {
          cin>>d;
          cout<<abs(sum(d))<<endl;
      }
  }

    return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 51.0

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