Submission #519200

#	Time	Username	Problem	Language	Result	Execution time	Memory
519200		XII	trapezoid (balkan11_trapezoid)	C++17	100 / 100	96 ms	7480 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "balkan11_trapezoid"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 1e5 + 1;
const int MOD = 30013;
int n;
vector<int> Y;
using pi = pair<int, int>;
pi save[N];
vector<pair<pi, pi>> ev;

pi bit[N * 2];

pi comb(const pi &a, const pi &b){
    return a.fi == b.fi ? mp(a.fi, (a.se + b.se) % MOD)
                        : (a.fi > b.fi) ? a : b;
}

void update(int i, const pi &v){
    while(i <= Y.size()){
        bit[i] = comb(bit[i], v);
        i += i & -i;
    }
}
pi query(int i){
    pi ans = {0, 0};
    while(1 <= i){
        ans = comb(ans, bit[i]);
        i -= i & -i;
    }
    return ans;
}

int getY(const int &y){
    return lower_bound(ALL(Y), y) - Y.begin() + 1;
}

int main(){
    IOS;
    Fi();
    cin >> n;
    Y.eb(0);
    FORU(i, 1, n){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        ev.eb(mp(a, c), mp(-1, i));
        ev.eb(mp(b, d), mp(+1, i));
        Y.eb(c), Y.eb(d);
    }
    sort(ALL(Y));
    Y.resize(unique(ALL(Y)) - Y.begin());
    sort(ALL(ev));
    pi ans = {0, 0};
    update(1, {0, 1});
    for(auto a: ev){
//        cout << a.fi.fi << " " << a.fi.se << "\n";
        if(a.se.fi == -1){
            save[a.se.se] = query(getY(a.fi.se));
            save[a.se.se].fi += 1;
            ans = comb(ans, save[a.se.se]);
        } else update(getY(a.fi.se), save[a.se.se]);
    }
    cout << ans.fi << " " << ans.se;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void update(int, const pi&)':
trapezoid.cpp:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(i <= Y.size()){
      |           ~~^~~~~~~~~~~
trapezoid.cpp: In function 'void Fi()':
trapezoid.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100