Submission #1124387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124387		InvMOD	Plahte (COCI17_plahte)	C++20	0 / 160	170 ms	16648 KiB

plahte

#include<bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define sz(v) (int)(v).size()


using namespace std;

using ll = long long;

const int N = 3e5+5;

struct Query{
    int op, x, y, sign, id;
    Query(int _op = 0, int _x = 0, int _y = 0, int _sign = 0, int _id = 0){
        op = _op,
        x = _x,
        y = _y,
        sign = _sign,
        id = _id;
    }

    bool operator < (const Query& q) const{
        return (x == q.x ? (y < q.y) : (x < q.x));
    };
};

struct Color{
    int x,y,k;
    Color(int x = 0, int y = 0, int k = 0): x(x), y(y), k(k) {}

    bool operator < (const Color& q) const{
        return (x == q.x ? (y < q.y) : (x < q.x));
    }
};

struct BIT{
    vector<int> bit;
    BIT(int n = 0): bit(n + 1) {}

    void update(int p, int val){
        for(; p < (int)bit.size(); p += p&-p){
            bit[p] += val;
        }
        return;
    }

    int get(int p){
        int res = 0;
        for(; p > 0; p -= p&-p){
            res += bit[p];
        }
        return res;
    }
};

int n, m;

void solve()
{
    cin >> n >> m;

    vector<Query> Quer; vector<int> compress;
    for(int i = 1; i <= n; i++){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        Quer.push_back(Query(1, x2, y2, +1, i));
        Quer.push_back(Query(1, x2, y1 - 1, -1, i));
        Quer.push_back(Query(1, x1 - 1, y2, -1, i));
        Quer.push_back(Query(1, x1 - 1, y1 - 1, +1, i));

        compress.push_back(x1),
        compress.push_back(y1),
        compress.push_back(x2),
        compress.push_back(y2),
        compress.push_back(x1 - 1),
        compress.push_back(y1 - 1);
    }

    vector<Color> pre_Color;
    for(int i = 1; i <= m; i++){
        int x,y,k; cin >> x >> y >> k;
        pre_Color.push_back(Color(x, y, k));
        compress.push_back(x),
        compress.push_back(y);
    }
    compress.push_back(-5);

    sort(all(compress)), compact(compress);
    for(Query cur_q : Quer){
        cur_q.x = lower_bound(all(compress), cur_q.x) - compress.begin();
        cur_q.y = lower_bound(all(compress), cur_q.y) - compress.begin();
    }
    for(Color cur_col : pre_Color){
        cur_col.x = lower_bound(all(compress), cur_col.x) - compress.begin();
        cur_col.y = lower_bound(all(compress), cur_col.y) - compress.begin();
    }

    sort(all(Quer)), sort(all(pre_Color));

    vector<Query> upd;
    map<int,int> pos_Color;

    for(Color e : pre_Color){
        int x = e.x, y = e.y, cur_col = e.k;
        if(pos_Color.count(cur_col)){
            if(pos_Color[cur_col] > y){
                upd.push_back(Query(-1, x, y, pos_Color[cur_col], 0));
            }
        }
        else{
            // x always >= previous color -> check if previous color y > current one or not
            pos_Color[cur_col] = y;
            upd.push_back(Query(1, x, y, 0, 0));
        }
    }

    auto ok_small = [&](Query x, Query y) -> bool{
        return (x < y || (x.x == y.x && x.y == y.y));
    };

    BIT bit(sz(compress)); vector<int> answer(n + 1);


    for(int i = 0, j = 0; i < sz(Quer); i++){
        while(j < sz(upd) && ok_small(upd[j], Quer[i])){
            if(upd[j].op < 0){
                // update 2 things: 1 position at sign and 1 position at y
                bit.update(upd[j].y, +1);
                bit.update(upd[j].sign, -1);
            }
            else{
                bit.update(upd[j].y, +1);
            }
            j++;
        }

        answer[Quer[i].id] += bit.get(Quer[i].y) * Quer[i].sign;
    }

    for(int i = 1; i <= n; i++){
        cout << answer[i] <<"\n";
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define task "task"
    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int32_t main()':
plahte.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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