Submission #843590

#	Time	Username	Problem	Language	Result	Execution time	Memory
843590		Cookie	Plahte (COCI17_plahte)	C++14	0 / 160	214 ms	44020 KiB

plahte

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>

const int mxn = 2e5 + 5;
const ll inf = 1e18, mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Q{
    int type, x, l, r, id;
    bool operator <(const Q &b){
        if(x != b.x)return(x < b.x);
        return(type > b.type);
    }
};
vt<Q>queries;
int n, m;
set<pair<int, int>>s;
map<int, int>colour[mxn + 1];
int ans[mxn + 1], k[mxn + 1], pa[mxn + 1];
ll area[mxn + 1];
vt<int>adj[mxn + 1];
void dfs(int s){
    if(s > n + 1){
        colour[s][k[s - (n + 1)]]++;
    }
    for(auto i: adj[s]){
        dfs(i);
        if(sz(colour[i]) > sz(colour[s]))swap(colour[i], colour[s]);
        for(auto j: colour[i]){
            colour[s][j.fi] += j.se;
        }
    }
    if(s <= n + 1){
        ans[s - 1] = sz(colour[s]);
    }
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    area[1] = 1e18 + 69420;
    s.insert(make_pair(-1e9 - 1, 1)); s.insert(make_pair(1e9 + 1, 1));
    for(int i = 1; i <= n; i++){
        ll a, b, c, d; cin >> a >> b >> c >> d;
        area[i + 1] = (c - a) * (d - b);
        queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
    }
    for(int i = 0; i < m; i++){
        int x, y; cin >> x >> y >> k[i];
        queries.pb({1, x, y, y, n + 2 + i}); queries.pb({-1, x, y, y, n + 2 + i});
    }
    sort(queries.begin(), queries.end());
    for(auto [type, x, l, r, id]: queries){
        if(type > 0){
        auto it = s.upper_bound(make_pair(l, -1));
        --it;
        int id1 = (*it).second;
        it = s.lower_bound(make_pair(r, -1));
        int id2 = (*it).second;
        //cout << id << " " << id1 << ' ' << id2 << "\n";
        if(id1 == id2){
            pa[id] = id1;
        }else{
            int cand1 = pa[id1], cand2 = pa[id2];
            if(cand1 == cand2){
                pa[id] = cand1;
            }else{
                if(area[cand1] > area[cand2]){
                    pa[id] = cand2;
                }else{
                    pa[id] = cand1;
                }
            }
        }
        s.insert(make_pair(l, id)); s.insert(make_pair(r, id));
        }else{
            s.erase(make_pair(l, id)); s.erase(make_pair(r, id));
        }
        
    }
    for(int i = 2; i < n + 2 + m; i++){
        //cout << i << " " << pa[i] << "\n";
        adj[pa[i]].pb(i);
    }
    dfs(1);
    for(int i = 1; i <= n; i++)cout << ans[i] << "\n";
    return(0);
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:63:24: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
   63 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                        ^
plahte.cpp:63:27: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
   63 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                           ^
plahte.cpp:63:30: warning: narrowing conversion of 'd' from 'long long int' to 'int' [-Wnarrowing]
   63 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                              ^
plahte.cpp:63:58: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   63 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                                                          ^
plahte.cpp:63:61: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
   63 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                                                             ^
plahte.cpp:63:64: warning: narrowing conversion of 'd' from 'long long int' to 'int' [-Wnarrowing]
   63 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                                                                ^
plahte.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto [type, x, l, r, id]: queries){
      |              ^

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