Submission #1124481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124481		InvMOD	Plahte (COCI17_plahte)	C++20	160 / 160	372 ms	64240 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;

struct RECT{
    int x1,y1,x2,y2;
    RECT(int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0): x1(x1), y1(y1), x2(x2), y2(y2) {}
};

struct Color{
    int x,y,k;
    Color(int x = 0, int y = 0, int k = 0): x(x), y(y), k(k) {}
};

struct SMT{
    int trsz;
    vector<int> st, laz;

    SMT(int n = 0): trsz(n), st((n << 2 | 1) + 1), laz((n << 2 | 1) + 1) {}

    void apply(int id, int val){
        laz[id] = val;
        st[id] = val;
        return;
    }

    void down(int id){
        int val = laz[id]; laz[id] = 0;
        if(!val) return;

        apply(id<<1, val);
        apply(id<<1|1, val);
        return;
    }

    void update(int id, int l, int r, int u, int v, int val){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            apply(id, val);
            return;
        }
        down(id);
        int m = l+r>>1;
        update(id<<1, l, m, u, v, val);
        update(id<<1|1, m+1, r, u, v, val);
        return;
    }

    int get(int id, int l, int r, int x){
        if(l == r){
            return st[id];
        }
        else{
            down(id);
            int m = l+r>>1;
            if(x <= m){
                return get(id<<1, l, m, x);
            }
            else return get(id<<1|1, m+1, r, x);
        }
        assert(1 == 0);
        return -1;
    }

    int get(int x){
        return get(1, 1, trsz, x);
    }

    void update(int l, int r, int val){
        return update(1, 1, trsz, l, r, val), void();
    }
};

void solve()
{
    int n,m; cin >> n >> m;

    vector<int> compress;

    vector<RECT> rect(n+1);
    for(int i = 1; i <= n; i++){
        cin >> rect[i].x1 >> rect[i].y1 >> rect[i].x2 >> rect[i].y2;
        compress.pb(rect[i].x1), compress.pb(rect[i].y1);
        compress.pb(rect[i].x2), compress.pb(rect[i].y2);
    }

    vector<Color> col(m+1);
    for(int i = 1; i <= m; i++){
        cin >> col[i].x >> col[i].y >> col[i].k;
        compress.pb(col[i].x), compress.pb(col[i].y);
    }
    compress.pb(-(1e9));

    sort(all(compress)), compact(compress);

    auto gid = [&](int x) -> int{
        return lower_bound(all(compress), x) - compress.begin();
    };

    vector<vector<pair<int,int>>> save(sz(compress), vector<pair<int,int>>());

    for(int i = 1; i <= n; i++){
        rect[i].x1 = gid(rect[i].x1), rect[i].x2 = gid(rect[i].x2);
        rect[i].y1 = gid(rect[i].y1), rect[i].y2 = gid(rect[i].y2);

        save[rect[i].x1].push_back(make_pair(rect[i].y1, -i-m));
        save[rect[i].x2].push_back(make_pair(rect[i].y2, +i+m));
    }

    for(int i = 1; i <= m; i++){
        col[i].x = gid(col[i].x), col[i].y = gid(col[i].y);
        save[col[i].x].push_back(make_pair(col[i].y, i));
    }

    vector<vector<int>> adj(sz(compress), vector<int>());

    SMT st(sz(compress)); st.update(1, sz(compress), -1);

    vector<int> par(n + 1); vector<set<int>> distinct(n+1, set<int>());
    for(int i = 0; i < sz(save); i++){
        sort(all(save[i]));

        for(pair<int,int> e : save[i]){
            int y = e.first, op = e.second;
            if(op < 0){
                int id = -(op + m); assert(id > 0);

                par[id] = st.get(y);
                st.update(rect[id].y1, rect[id].y2, id);
            }
            else if(op <= m){
                int cpar = st.get(y);
                if(cpar > 0){
                    assert(op <= m && cpar <= n);
                    distinct[cpar].insert(col[op].k);
                }
            }
            else{
                int id = op - m; assert(op > m && id <= n);

                st.update(rect[id].y1, rect[id].y2, par[id]);
            }
        }
    }

    for(int i = 1; i <= n; i++) if(par[i] != -1) adj[par[i]].push_back(i);

    vector<int> answer(n + 1);
    auto dfs = [&](auto&& dfs, int x, int p) -> void{
        for(int v : adj[x]){
            dfs(dfs, v, x);

            if(sz(distinct[v]) > sz(distinct[x])){
                swap(distinct[v], distinct[x]);
            }

            for(int i : distinct[v]) distinct[x].insert(i);
        }

        answer[x] = distinct[x].size();
        return;
    };

    for(int i = 1; i <= n; i++){
        if(par[i] < 0) dfs(dfs, i, -1);
    }

    for(int i = 1; i <= n; i++)
        cout << answer[i] <<"\n";

    return;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:205:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32