제출 #144509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144509		arnold518	Employment (JOI16_employment)	C++14	30 / 100	506 ms	16564 KiB

employment

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXVAL = 4e5;
const int INF = 2147483647;

struct Data { int t, a, b; };

int N, Q, A[MAXN+10];
Data B[MAXN+10];
int tree[4*MAXVAL+10];
vector<int> comp, comp2;

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }
int getcomp2(int x) { return *lower_bound(comp2.begin(), comp2.end(), x); }

void update(int node, int tl, int tr, int l, int r, int val)
{
	if(l>r) return;
	if(tr<l || r<tl) return;
	if(l<=tl && tr<=r)
	{
        tree[node]+=val;
        return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, val);
	update(node*2+1, mid+1, tr, l, r, val);
}

int query(int node, int tl, int tr, int pos)
{
	if(tl==tr) return tree[node];
	int mid=tl+tr>>1;
	if(pos<=mid) return tree[node]+query(node*2, tl, mid, pos);
	else return tree[node]+query(node*2+1, mid+1, tr, pos);
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]), comp.push_back(A[i]+1), comp2.push_back(A[i]);
    for(i=1; i<=Q; i++)
    {
    	scanf("%d", &B[i].t);
    	if(B[i].t==1) scanf("%d", &B[i].a);
    	else scanf("%d%d", &B[i].a, &B[i].b), comp.push_back(B[i].b), comp.push_back(B[i].b+1), comp2.push_back(B[i].b);
    }
    comp.push_back(INF); comp.push_back(1); comp2.push_back(INF); comp2.push_back(0);
    sort(comp.begin(), comp.end()); sort(comp2.begin(), comp2.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end()); comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());

    for(i=1; i<=N+1; i++)
    {
    	int a=min(A[i], A[i-1])+1, b=max(A[i], A[i-1]);
    	update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
    }

    for(i=1; i<=Q; i++)
    {
        if(B[i].t==1) printf("%d\n", query(1, 1, comp.size(), getcomp(getcomp2(B[i].a)))/2);
        else
        {
            int a, b;
            a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), -1);
            a=min(A[B[i].a], A[B[i].a+1])+1, b=max(A[B[i].a], A[B[i].a+1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), -1);
            A[B[i].a]=B[i].b;
            a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
            a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

employment.cpp: In function 'void update(int, int, int, int, int, int)':
employment.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
employment.cpp: In function 'int query(int, int, int, int)':
employment.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
employment.cpp: In function 'int main()':
employment.cpp:46:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
employment.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:49:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]), comp.push_back(A[i]+1), comp2.push_back(A[i]);
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
employment.cpp:52:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &B[i].t);
      ~~~~~^~~~~~~~~~~~~~~
employment.cpp:53:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      if(B[i].t==1) scanf("%d", &B[i].a);
                    ~~~~~^~~~~~~~~~~~~~~
employment.cpp:54:92: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      else scanf("%d%d", &B[i].a, &B[i].b), comp.push_back(B[i].b), comp.push_back(B[i].b+1), comp2.push_back(B[i].b);
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60