Submission #1067311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067311		vjudge1	Plahte (COCI17_plahte)	C++17	160 / 160	225 ms	55632 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = b; i >= a; --i)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define REPD(i, a, b) for(int i = b; i > a; -- i)
#define ALL(v) v.begin(),v.end()
#define next __next
#define left __left
#define right __right
#define prev __prev
const int MOD[6] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277, 998244353};
const int BASE[6] = {23309, 300, 330, 280, 2309, 256};
const int base = BASE[0];
const int mod = MOD[0];
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
void minimize(int &u, int v){
    if(u > v) u = v;
}
void maximize(int &u, int v){
    if(u < v) u = v;
}
void minimizell(long long &u, long long v){
    if(u > v) u = v;
}
void maximizell(long long &u, long long v){
    if(u < v) u = v;
}
const int maxN = 3e5 + 2;
const int maxM = 1e5 + 2;
const int maxK = 1e2 + 2;
const int INF = 1e9 + 8;
const long long INFLL = 1e18;
const int LOG = 16;
vector<int> adj[maxN];
int N, M;
struct Event{
    int x, yA, yB, type, id;
}seg[2 * maxN];
// 3 phai sau 1 va truoc 2
// 1 3 2
bool cmp(const Event &A, const Event &B){
    if(A.x != B.x) return A.x < B.x;
    return A.type > B.type;
}
int comp[3 * maxN];// compress array
int par[maxN];
int curNode = 0;
set<int> col[maxN];
int it[12 * maxN];
int lazy[12 * maxN];
void build(int id, int l, int r){
    if(l == r){
        lazy[id] = -1;
        return ;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    lazy[id] = -1;
}
void push(int id){
    lazy[id << 1] = lazy[id << 1 | 1] = it[id << 1] = it[id << 1 | 1] = lazy[id];
    lazy[id] = -1;
}
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){
        it[id] = val;
        lazy[id] = val;
        return ;
    }
    int mid = l + r >> 1;
    if(lazy[id] != -1)push(id);
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
}
int get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(l >= u && r <= v){
        return it[id];
    }
    int mid = l + r >> 1;
    if(lazy[id] != -1)push(id);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
int res[maxN];
void dfs(int u){
    for(int v : adj[u]){
        dfs(v);
        if(col[v].size() > col[u].size())swap(col[u], col[v]);
        for(set<int> :: iterator it = col[v].begin(); it != col[v].end(); ++it)col[u].insert(*it);
        col[v].clear();
    }
    res[u] = col[u].size();
}
int degIn[maxN];
int main(){
//    freopen("Plahte.INP", "r", stdin);
//    freopen("Plahte.OUT", "w", stdout);
    //freopen(".INP", "w", stdout);
    //freopen(".ANS", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> M;
    int cnt = 0, cntEvent = 0;
    FOR(i, 1, N){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        comp[++cnt] = b;
        comp[++cnt] = d;
        seg[++cntEvent] = {a, b, d, 1, i};
        seg[++cntEvent] = {c, b, d, -1, i};
    }

    FOR(i, 1, M){
        int x, y, k;
        cin >> x >> y >> k;
        comp[++cnt] = y;
        seg[++cntEvent] = {x, y, y, 0, k};
    }
    sort(comp + 1, comp + 1 + cnt);

//    cnt = 20;

    sort(seg + 1, seg + 1 + cntEvent, cmp);
//    for(int i = 1; i <= cntEvent; ++i)cout << seg[i].x << ' ' << seg[i].yA << ' ' << seg[i].yB << ' ' << seg[i].type << ' ' << seg[i].id << "\n";
    FOR(i, 1, cntEvent){
        Event &tmp = seg[i];
        tmp.yA = lower_bound(comp + 1, comp + 1 + cnt, tmp.yA) - comp;
        tmp.yB = lower_bound(comp + 1, comp + 1 + cnt, tmp.yB) - comp;
        if(tmp.type == 1){

            int p = get(1, 1, cnt, tmp.yA, tmp.yB);
            if(p > 0){
                adj[p].push_back(tmp.id);
                par[tmp.id] = p;
                degIn[tmp.id]++;
            }
            update(1, 1, cnt, tmp.yA, tmp.yB, tmp.id);
//            addSegment(1, 1, cnt, tmp.yA, tmp.yB, tmp.id);
        }
        else if(tmp.type == -1){

            update(1, 1, cnt, tmp.yA, tmp.yB, par[tmp.id]);
//            cout << inRec(1, 1, cnt, tmp.yA, tmp.yB) << "\n";
//            FOR(i, tmp.yA, tmp.yB)cout << inRec(1, 1, cnt, i, i) << ' ';cout << "\n";
        }
        else{
            int node = get(1, 1, cnt, tmp.yA, tmp.yB);
            if(node > 0){
                col[node].insert(tmp.id);
            }
        }
    }
    for(int i = 1; i <= N; ++i){
        if(degIn[i] == 0)dfs(i);
    }
    FOR(i, 1, N)cout << res[i] << '\n';
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void build(int, int, int)':
plahte.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = l + r >> 1;
      |               ~~^~~
plahte.cpp: In function 'void update(int, int, int, int, int, int)':
plahte.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = l + r >> 1;
      |               ~~^~~
plahte.cpp: In function 'int get(int, int, int, int, int)':
plahte.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int mid = l + r >> 1;
      |               ~~^~~

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