oj.uz

답안 #603341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603341 2022-07-24T03:49:11 Z Do_you_copy Plahte (COCI17_plahte) C++17
32 / 160
 247 ms 33472 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 <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
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 int maxN = 1e5 + 1;
const int inf = 0x3f3f3f3f;
int n, m;


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

vector <int> node;

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

TNode st[maxN * 8];

void pull(int 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(int id, int i, int j, int val, int l = 1, int 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);
    int mid = (l + r) / 2;
    update(id * 2, i, j, val, l, mid);
    update(id * 2 + 1, i, j, val, mid + 1, r);
}

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

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

struct TQuery{
    int x, y, v, idx, t;
};
vector <TQuery> q;
void Init(){
    cin >> n >> m;
    for (int 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);
    sort(node.begin(), node.end());
    for (int i = 1; i <= m; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        q.pb({x, y, z, i, 1});
    }
    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){
            int low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
            int high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
            update(1, low, high, par[i.idx]);
        }
        if (!i.t){
            int low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
            int high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
            int k = get(1, low);
            adj[k].pb(i.idx);
            par[i.idx] = k;
            update(1, low, high, i.idx);
        }
        if (i.t == 1){
            int low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
            int k = get(1, low);
            color[k].insert(i.v);
        }
    }
    color[0].clear();
    dfs(0);
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
}


int 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 78 ms 18648 KB Output is correct
2 Correct 78 ms 19392 KB Output is correct
3 Correct 7 ms 13728 KB Output is correct

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 20312 KB Output is correct
2 Incorrect 97 ms 19564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 169 ms 26116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 247 ms 33472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 242 ms 31556 KB Output isn't correct
2 Halted 0 ms 0 KB -