oj.uz

Submission #843605

# Submission time Handle Problem Language Result Execution time Memory
843605 2023-09-04T08:25:37 Z Cookie Plahte (COCI17_plahte) C++14
160 / 160
 206 ms 42672 KB 
#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]);
        
    }
}
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

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

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25024 KB Output is correct
2 Correct 57 ms 25536 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 26048 KB Output is correct
2 Correct 77 ms 25412 KB Output is correct
3 Correct 5 ms 18268 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 32952 KB Output is correct
2 Correct 114 ms 30392 KB Output is correct
3 Correct 5 ms 18268 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 42672 KB Output is correct
2 Correct 199 ms 38236 KB Output is correct
3 Correct 5 ms 18264 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 40876 KB Output is correct
2 Correct 206 ms 38020 KB Output is correct
3 Correct 4 ms 18524 KB Output is correct