oj.uz

답안 #37231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37231 2017-12-22T18:47:42 Z Ulugbek_Abdimanabov Simple game (IZhO17_game) C++14
0 / 100
 1000 ms 23716 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 a[N],t[4*N];
int n;
void build(int v=1, int tl=1, int tr=n)
{
            if(tl==tr)t[v]=a[tl];
            else
            {
                int tm=(tl+tr)>>1;
                build(v+v,tl,tm);
                build(v+v+1,tm+1,tr);
                t[v]=t[v+v]+t[v+v+1];
            }
}

int sum(int l,int r,int v=1, int tl=1, int tr=N)
{
    if(tl>r||tr<l)return 0;
    if(tl>=l&&tr<=r)return t[v];
    int tm=(tl+tr)>>1;
    return sum(l,r,v+v,tl,tm)+sum(l,r,v+v+1,tm+1,tr);
}

void updatem(int l, int r, int tl=1, int tr=N, int v=1)
{
    if(tl>r||tr<l)return;
    if(tl>=l&&tr<=r){t[v]-=(tr-tl+1); }
    if(tl==tr)return;
    int tm=(tl+tr)>>1;
    updatem(l,r,tl,tm,v+v);
    updatem(l,r,tm+1,tr,v+v+1);
    t[v]=t[v+v]+t[v+v+1];
}
void updatep(int l, int r,  int tl=1, int tr=N, int v=1)
{
    if(tl>r||tr<l)return;
    if(tl>=l&&tr<=r){t[v]+=(tr-tl+1); }
    if(tl==tr)return;
    int tm=(tl+tr)>>1;
    updatep(l,r,tl,tm,v+v);
    updatep(l,r,tm+1,tr,v+v+1);
    t[v]=t[v+v]+t[v+v+1];
}


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

		int m; cin>>n>>m;
		rep(i,1,n+1)cin>>a[i];
		rep(i,1,n)
		    updatep(min(a[i],a[i+1]),max(a[i],a[i+1]));

            rep(i,0,m)
            {
                int j; cin>>j;
                if(j==2)
                {
                    int l; cin>>l;
                    cout<<sum(l,l)<<endl;
                }
                else
                {
                    int l,r; cin>>l>>r;
                    updatem(min(a[i],a[i+1]),max(a[i],a[i+1]));
                    a[l]=r;
                    updatep(min(a[i],a[i+1]),max(a[i],a[i+1]));
                }

            }


    return 0;
}

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23716 KB Output is correct
2 Execution timed out 1000 ms 23716 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23716 KB Output is correct
2 Execution timed out 1000 ms 23716 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23716 KB Output is correct
2 Execution timed out 1000 ms 23716 KB Execution timed out
3 Halted 0 ms 0 KB -