Submission #849292

#	Time	Username	Problem	Language	Result	Execution time	Memory
849292		mickey080929	Employment (JOI16_employment)	C++17	100 / 100	264 ms	17920 KiB

employment

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
typedef pair<int,int> pii;

struct SegmentTree{
    vector<int> tree, lazy;
    void init(int n) {
        tree.resize(n*4+1);
        fill(tree.begin(), tree.end(), 0);
    }
    void update(int node, int s, int e, int tar, int val) {
        if (s > tar || tar > e) return;
        tree[node] += val;
        if (s == e) return;
        int mid = s + e >> 1;
        update(node*2, s, mid, tar, val);
        update(node*2+1, mid+1, e, tar, val);
    }
    int query(int node, int s, int e, int l, int r) {
        if (l > e || s > r) return 0;
        if (l <= s && e <= r) return tree[node];
        int mid = s + e >> 1;
        return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
    }
} seg;

struct Query{
    int k, a, b;
};

int N, M, Q;
int a[200010];
int w[200010];
Query q[200010];

void Update(int i) {
    int cnt = 0;
    if (i > 1 && a[i-1] > a[i]) cnt ++;
    if (i < N && a[i+1] >= a[i]) cnt ++;
    if (cnt == 0) seg.update(1, 1, M, a[i], 1-w[i]), w[i]=1;
    else if (cnt == 1) seg.update(1, 1, M, a[i], -w[i]), w[i]=0;
    else seg.update(1, 1, M, a[i], -1-w[i]), w[i]=-1; // cnt == 2
}

int main() {
    scanf("%d %d", &N, &Q);
    vector<int> t;
    for (int i=1; i<=N; i++) {
        scanf("%d", &a[i]);
        t.push_back(a[i]);
    }
    for (int i=1; i<=Q; i++) {
        scanf("%d", &q[i].k);
        if (q[i].k == 1) {
            scanf("%d", &q[i].a);
            q[i].b = 0;
            t.push_back(q[i].a);
        }
        else {
            scanf("%d %d", &q[i].a, &q[i].b);
            t.push_back(q[i].b);
        }
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    for (int i=1; i<=N; i++) {
        a[i] = lower_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
    }
    for (int i=1; i<=Q; i++) {
        if (q[i].k == 1)
            q[i].a = lower_bound(t.begin(), t.end(), q[i].a) - t.begin() + 1;
        else
            q[i].b = lower_bound(t.begin(), t.end(), q[i].b) - t.begin() + 1;
    }
    M = (int) t.size();
    seg.init(M);
    for (int i=1; i<=N; i++) Update(i);
    for (int i=1; i<=Q; i++) {
        if (q[i].k == 1) {
            printf("%d\n", seg.query(1, 1, M, q[i].a, M));
        }
        else {
            seg.update(1, 1, M, a[q[i].a], -w[q[i].a]);
            w[q[i].a] = 0;
            a[q[i].a] = q[i].b;
            Update(q[i].a);
            if (q[i].a > 1) Update(q[i].a - 1);
            if (q[i].a < N) Update(q[i].a + 1);
        }
    }

    return 0;
}

Compilation message (stderr)

employment.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
employment.cpp:19:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         int mid = s + e >> 1;
      |                   ~~^~~
employment.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
employment.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = s + e >> 1;
      |                   ~~^~~
employment.cpp: In function 'int main()':
employment.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
employment.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
employment.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d", &q[i].k);
      |         ~~~~~^~~~~~~~~~~~~~~
employment.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |             scanf("%d", &q[i].a);
      |             ~~~~~^~~~~~~~~~~~~~~
employment.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d %d", &q[i].a, &q[i].b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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