Submission #238291

#	Time	Username	Problem	Language	Result	Execution time	Memory
238291		egekabas	Hamburg Steak (JOI20_hamburg)	C++14	1 / 100	488 ms	93248 KiB

hamburg

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct rect{
    int x1, y1, x2, y2;
};
int lazy[800009];
pii seg[800009];
void push(int v){
    seg[2*v].ff += lazy[v];
    seg[2*v+1].ff += lazy[v];
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    lazy[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val){
    if(r < tl || tr < l)
        return;
    if(l <= tl && tr <= r){
        seg[v].ff += val;
        lazy[v] += val;
    }
    else{
        push(v);
        upd(2*v, tl, (tl+tr)/2, l, r, val);
        upd(2*v+1, (tl+tr)/2+1, tr, l, r, val);
        seg[v] = max(seg[2*v], seg[2*v+1]);
    }
}
void build(int v, int tl, int tr){
    if(tl == tr){
        seg[v] = {0, tl};
        return;
    }
    build(2*v, tl, (tl+tr)/2);
    build(2*v+1, (tl+tr)/2+1, tr);
    seg[v] = max(seg[2*v], seg[2*v+1]);
}
vector<int> ycord;
vector<int> xcord;
int yc(int x){return lower_bound(ycord.begin(), ycord.end(), x)-ycord.begin();}
int xc(int x){return lower_bound(xcord.begin(), xcord.end(), x)-xcord.begin();}

vector<pii> add[400009];
vector<pii> del[400009];
int n, k;
rect ar[200009];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        cin >> ar[i].x1 >> ar[i].y1 >> ar[i].x2 >> ar[i].y2;
        ycord.pb(ar[i].y1);
        ycord.pb(ar[i].y2);
        xcord.pb(ar[i].x1);
        xcord.pb(ar[i].x2);
    }
    sort(ycord.begin(), ycord.end());
    ycord.resize(unique(ycord.begin(), ycord.end())-ycord.begin());
    sort(xcord.begin(), xcord.end());
    xcord.resize(unique(xcord.begin(), xcord.end())-xcord.begin());
    for(int i = 0; i < n; ++i)
        ar[i] = {xc(ar[i].x1), yc(ar[i].y1), xc(ar[i].x2), yc(ar[i].y2)};
    vector<pii> ans;
    while(k--){
        build(1, 0, ycord.size()-1);
        for(int i = 0; i < n; ++i)
            if(ar[i].x1 >= 0){
                add[ar[i].x1].pb({ar[i].y1, ar[i].y2});
                del[ar[i].x2].pb({ar[i].y1, ar[i].y2});
            }
        pair<int, pii> curans = {0, {0, 0}};
        for(int i = 0; i < xcord.size(); ++i){
            for(auto u : add[i])
                upd(1, 0, ycord.size()-1, u.ff, u.ss, 1);
            curans = max(curans, {seg[1].ff, {i, seg[1].ss}});
            for(auto u : del[i])
                upd(1, 0, ycord.size()-1, u.ff, u.ss, -1);
            add[i].clear();
            del[i].clear();
        }
        ans.pb(curans.ss);
        pii pt = curans.ss;
        for(int i = 0; i < n; ++i)
            if(ar[i].x1 <= pt.ff && pt.ff <= ar[i].x2 && ar[i].y1 <= pt.ss && pt.ss <= ar[i].y2)
                ar[i] = {-1, -1, -1, -1};
    }
    //for(int i = 0; i < n; ++i)
    //    assert(ar[i].x1 < 0);
    for(auto u : ans)
        cout << xcord[u.ff] << ' ' << ycord[u.ss] << '\n';
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i = 0; i < xcord.size(); ++i){
      |                        ~~^~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79