oj.uz

답안 #603352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603352 2022-07-24T04:16:49 Z Do_you_copy Plahte (COCI17_plahte) C++17
160 / 160
 342 ms 60820 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const ll maxN = 1e5 + 1;
const ll inf = 0x3f3f3f3f;
ll n, m;


struct TRect{
    ll x, y, u, v;
};
TRect a[maxN];

vector <ll> node;

struct TNode{
    ll lazy, val;
    TNode() : lazy(-1), val(0){}
};

TNode st[maxN * 16];

void pull(ll id){
    if (st[id].lazy != -1){
        st[id * 2].lazy = st[id * 2 + 1].lazy = st[id].lazy;
        st[id * 2].val = st[id * 2 + 1].val = st[id].lazy;
        st[id].lazy = -1;
    }
}

void update(ll id, ll i, ll j, ll val, ll l = 1, ll r = node.size()){
    if (r < i || l > j) return;
    if (i <= l && r <= j){
        st[id].val = val;
        st[id].lazy = val;
        return;
    }
    pull(id);
    ll mid = (l + r) / 2;
    update(id * 2, i, j, val, l, mid);
    update(id * 2 + 1, i, j, val, mid + 1, r);
}

ll get(ll id, ll i, ll l = 1, ll r = node.size()){
    if (r < i || l > i) return 0;
    if (l == r) return st[id].val;
    pull(id);
    ll mid = (l + r) / 2;
    return get(id * 2, i, l, mid) | get(id * 2 + 1, i, mid + 1, r);
}

vector <ll> adj[maxN];
set <ll> color[maxN];
ll par[maxN];
ll ans[maxN];
void dfs(ll u){
    for (ll i: adj[u]){
        dfs(i);
        if (color[u].size() < color[i].size()) swap(color[u], color[i]);
        for (ll j: color[i]) color[u].insert(j);
    }
    ans[u] = color[u].size();
}

struct TQuery{
    ll x, y, v, idx, t;
};
vector <TQuery> q;
void Init(){
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y >> a[i].u >> a[i].v;
        q.pb({a[i].x, a[i].y, a[i].v, i, 0});
        q.pb({a[i].u, a[i].y, a[i].v, i, 2});
        node.pb(a[i].y);
        node.pb(a[i].v);
    }
    node.pb(0); node.pb(inf);
    for (ll i = 1; i <= m; ++i){
        ll x, y, z;
        cin >> x >> y >> z;
        q.pb({x, y, z, i, 1});
        node.pb(y);
    }
    sort(node.begin(), node.end());
    sort(q.begin(), q.end(),[](const auto &i, const auto &j){
        if (i.x == j.x){
            return i.t < j.t;
         }
         return i.x < j.x;
    });
    for (auto i : q){
        if (i.t == 2){
            ll low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
            ll high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
            update(1, low, high, par[i.idx]);
        }
        if (!i.t){
            ll low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
            ll high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
            ll k = get(1, low);
            adj[k].pb(i.idx);
            par[i.idx] = k;
            update(1, low, high, i.idx);
        }
        if (i.t == 1){
            ll low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
            ll k = get(1, low);
            color[k].insert(i.v);
        }
    }
    color[0].clear();
    dfs(0);
    for (ll i = 1; i <= n; ++i) cout << ans[i] << "\n";
}

signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 40080 KB Output is correct
2 Correct 95 ms 40732 KB Output is correct
3 Correct 20 ms 32340 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 42236 KB Output is correct
2 Correct 119 ms 41672 KB Output is correct
3 Correct 15 ms 32340 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 50136 KB Output is correct
2 Correct 184 ms 50084 KB Output is correct
3 Correct 16 ms 32340 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 330 ms 60412 KB Output is correct
2 Correct 310 ms 60820 KB Output is correct
3 Correct 15 ms 32420 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 58360 KB Output is correct
2 Correct 342 ms 60664 KB Output is correct
3 Correct 15 ms 32416 KB Output is correct