oj.uz

Submission #487740

# Submission time Handle Problem Language Result Execution time Memory
487740 2021-11-16T14:09:09 Z LptN21 Plahte (COCI17_plahte) C++14
160 / 160
 446 ms 86660 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define PI acos(-1.0)
#define FF first
#define SS second
#define eps 1e-9
// vector
#define pb push_back
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define lb lower_bound
#define ub upper_bound
// bit
#define CNTBIT(x) __builtin_popcount(x)
#define ODDBIT(x) __builtin_parity(x)
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
// typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
/* CODE BELOW */
const int N=160000+7, M=18;
const int MOD=1e9+7;
const int oo=1e9+9;

int n, m, k, t;

struct Node{
    int x, y, idx; Node() {}
    Node(int _x, int _y, int i):
        x(_x), y(_y), idx(i) {}
    bool operator<(const Node &e) const {
        if(x!=e.x) return x<e.x;
        if(y!=e.y) return y<e.y;
        return idx>e.idx;
    }
};

set<int> color[N];
int ans[N];
int x1_[N], y1_[N];
int x2_[N], y2_[N];
vector<int> adj[N];

bool mark[N];
vector<ii> st[N<<2];

void update(int idx, int l0, int r0, int p, ii v) { // first: val, second: idx
    st[idx].pb(v);
    if(l0==r0) return;
    int mid=(l0+r0)/2;
    if(p<=mid) update(idx*2, l0, mid, p, v);
    else update(idx*2+1, mid+1, r0, p, v);
}

void addEdge(int idx, int l0, int r0, int l, int r, ii v) {
    if(l0>r||r0<l) return;
    if(l<=l0&&r0<=r) {
        while(sz(st[idx])&&st[idx].back().FF>=v.FF) {
            int j=st[idx].back().SS;
            if(!mark[j]) {
                mark[j]=1;
                adj[v.SS].pb(j);
            }

            st[idx].pop_back();
        }
        return;
    }
    int mid=(l0+r0)/2;

    addEdge(idx*2, l0, mid, l, r, v);
    addEdge(idx*2+1, mid+1, r0, l, r, v);
}

vector<int> b;
void upd(int p, ii v) {
    update(1, 1, sz(b), p, v);
}
void _add(int l, int r, ii v) {
    addEdge(1, 1, sz(b), l, r, v);
}

int dfs(int u) {
    int r=u;
    for(int v:adj[u]) {
        v=dfs(v);
        if(sz(color[r])<sz(color[v])) swap(r, v);
        for(int x:color[v]) color[r].insert(x);
    }
    ans[u]=sz(color[r]);
    return r;
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) {
        scanf("%d%d", &x1_[i], &y1_[i]);
        scanf("%d%d", &x2_[i], &y2_[i]);
        b.pb(y1_[i]), b.pb(y2_[i]);
    }
    for(int i=n+1;i<=n+m;i++) {
        scanf("%d%d%d", &x1_[i], &y1_[i], &k);
        x2_[i]=x1_[i], y2_[i]=y1_[i], b.pb(y1_[i]);
        color[i].insert(k);
    }
    x1_[n+m+1]=y1_[n+m+1]=0;
    x2_[n+m+1]=y2_[n+m+1]=oo;
    b.pb(0), b.pb(oo);
    sort(all(b)), b.resize(unique(all(b))-b.begin());

    vector<Node> ev;
    for(int i=1;i<=n+m+1;i++) {
        y1_[i]=lb(all(b), y1_[i])-b.begin()+1;
        y2_[i]=lb(all(b), y2_[i])-b.begin()+1;
        ev.pb(Node(x2_[i], y2_[i], i));
    }
    sort(all(ev));

    for(Node &e:ev) {
        int i=e.idx;
        _add(y1_[i], y2_[i], ii(x1_[i], i));
        upd(y2_[i], ii(x2_[i], i));
    }
    dfs(n+m+1);

    for(int i=1;i<=n;i++) printf("%d\n", ans[i]);

    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special/edge cases (n=1?)
    - do smth instead of nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%d%d", &x1_[i], &y1_[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%d%d", &x2_[i], &y2_[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf("%d%d%d", &x1_[i], &y1_[i], &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 45116 KB Output is correct
2 Correct 128 ms 45632 KB Output is correct
3 Correct 13 ms 26616 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 48648 KB Output is correct
2 Correct 136 ms 47020 KB Output is correct
3 Correct 13 ms 26604 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 64092 KB Output is correct
2 Correct 235 ms 60132 KB Output is correct
3 Correct 15 ms 26616 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 86660 KB Output is correct
2 Correct 446 ms 82384 KB Output is correct
3 Correct 13 ms 26708 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 84680 KB Output is correct
2 Correct 424 ms 82460 KB Output is correct
3 Correct 13 ms 26600 KB Output is correct