Submission #843604

#TimeUsernameProblemLanguageResultExecution timeMemory
843604CookiePlahte (COCI17_plahte)C++14
32 / 160
196 ms43268 KiB
#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) - 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]); if(s == 2){ for(auto i: colour[s]){ cout << i.fi << " "; assert(i.se); } } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; area[1] = 1e18 + 69420; pa[1] = 1; s.insert(make_pair(0, 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 + 1) * (d - b + 1); 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, -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; } } } if(type == 2){ s.insert(make_pair(l, id)); s.insert(make_pair(r, id)); } }else{ if(type == -2){ s.erase(make_pair(l, id)); s.erase(make_pair(r, id)); } } } int cnt = 0; 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:70:24: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
   70 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                        ^
plahte.cpp:70:27: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
   70 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                           ^
plahte.cpp:70:30: warning: narrowing conversion of 'd' from 'long long int' to 'int' [-Wnarrowing]
   70 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                              ^
plahte.cpp:70:58: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   70 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                                                          ^
plahte.cpp:70:61: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
   70 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                                                             ^
plahte.cpp:70:64: warning: narrowing conversion of 'd' from 'long long int' to 'int' [-Wnarrowing]
   70 |         queries.pb({2, a, b, d, i + 1}); queries.pb({-2, c, b, d, i + 1});
      |                                                                ^
plahte.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [type, x, l, r, id]: queries){
      |              ^
plahte.cpp:111:9: warning: unused variable 'cnt' [-Wunused-variable]
  111 |     int cnt = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...