oj.uz

Submission #866016

# Submission time Handle Problem Language Result Execution time Memory
866016 2023-10-25T09:51:57 Z hafo Plahte (COCI17_plahte) C++14
160 / 160
 318 ms 101820 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 3e5 + 7;
const ll oo = 1e18 + 69;

int n, m, p[2][maxn], res[maxn];
vector<int> g[maxn], c[maxn];
set<int> s[maxn];

struct rec {
    int x, y, u, v;
} a[maxn];

struct query {
    int x, y, k;
} que[maxn];

vector<int> vx, vy, ev[4][maxn];

int idx(int x) {
    return lower_bound(all(vx), x) - vx.begin();
}

int idy(int y) {
    return lower_bound(all(vy), y) - vy.begin() + 1;
}

struct ST {
    int st[4 * maxn], lz[4 * maxn];

    void init(int n) {
        for(int i = 1; i <= 4 * n; i++) {
            st[i] = 0;
            lz[i] = -1;
        }
    }

    void fix(int id, int l, int r) {
        if(lz[id] == -1) return;
        if(l == r) st[id] = lz[id];
        else {
            lz[id << 1] = lz[id];
            lz[id << 1 | 1] = lz[id];
        }
        lz[id] = -1;
    }

    void update(int id, int l, int r, int u, int v, int val) {
        fix(id, l, r);
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            lz[id] = val;
            fix(id, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
    }

    int get(int id, int l, int r, int pos) {
        fix(id, l, r);
        if(pos < l || pos > r) return 0;
        if(l == r) return st[id];
        int mid = l + r >> 1;
        return get(id << 1, l, mid, pos) + get(id << 1 | 1, mid + 1, r, pos);        
    }

} st;

void dfs(int u, int par) {
    for(auto v:g[u]) {
        if(v == par) continue;
        dfs(v, u);
        if(Size(s[u]) < Size(s[v])) s[u].swap(s[v]);
        for(auto i:s[v]) s[u].insert(i);
    }
    res[u] = Size(s[u]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m;
    for(int i = 1; i <= n; i++) {
        cin>>a[i].x>>a[i].y>>a[i].u>>a[i].v;
        vx.pb(a[i].x);
        vx.pb(a[i].u);
        vy.pb(a[i].y);
        vy.pb(a[i].v);
    }

    for(int i = 1; i <= m; i++) {
        cin>>que[i].x>>que[i].y>>que[i].k;
        vx.pb(que[i].x);
        vy.pb(que[i].y);
    }

    sort(all(vx));
    sort(all(vy));
    vx.erase(unique(all(vx)), vx.end());
    vy.erase(unique(all(vy)), vy.end());

    for(int i = 1; i <= n; i++) {
        int id = idx(a[i].x);
        ev[0][id].pb(i);
        id = idx(a[i].u);
        ev[1][id].pb(i);
    }
    for(int i = 1; i <= m; i++) {
        int id = idx(que[i].x);
        ev[2][id].pb(i);
    }

    st.init(Size(vy));
    for(int i = 0; i < Size(vx); i++) {        
        for(auto j:ev[0][i]) {
            int l = idy(a[j].y);
            int r = idy(a[j].v);
            p[0][j] = st.get(1, 1, Size(vy), l);
            st.update(1, 1, Size(vy), l, r, j);
        }

        for(auto j:ev[2][i]) {
            int id = idy(que[j].y);
            p[1][j] = st.get(1, 1, Size(vy), id);
        }

        for(auto j:ev[1][i]) {
            int l = idy(a[j].y);
            int r = idy(a[j].v);
            st.update(1, 1, Size(vy), l, r, p[0][j]);
        }
    }

    for(int i = 1; i <= n; i++) {
        g[p[0][i]].pb(i);
    }

    for(int i = 1; i <= m; i++) {
        if(p[1][i] == 0) continue;
        s[p[1][i]].insert(que[i].k);
    }
    
    dfs(0, 0);
    for(int i = 1; i <= n; i++) cout<<res[i]<<"\n";
    return 0;
}

Compilation message

plahte.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
plahte.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~
plahte.cpp: In member function 'int ST::get(int, int, int, int)':
plahte.cpp:81:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 77744 KB Output is correct
2 Correct 115 ms 78316 KB Output is correct
3 Correct 13 ms 66140 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 79584 KB Output is correct
2 Correct 119 ms 78904 KB Output is correct
3 Correct 13 ms 66136 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 91320 KB Output is correct
2 Correct 188 ms 85696 KB Output is correct
3 Correct 13 ms 65884 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 101820 KB Output is correct
2 Correct 318 ms 96964 KB Output is correct
3 Correct 13 ms 65880 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 99492 KB Output is correct
2 Correct 309 ms 95556 KB Output is correct
3 Correct 13 ms 66140 KB Output is correct