Submission #1126461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126461		InvMOD	trapezoid (balkan11_trapezoid)	C++20	100 / 100	109 ms	11320 KiB

trapezoid

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

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

namespace modulo_function{
    const int _modulo = 30013; // modulo

    int add(int x, int y){
        return (x + y < _modulo ? x + y : x + y - _modulo);
    }

    int mul(int x, int y){
        return (1ll * x * y) % _modulo;
    }

    int sub(int x, int y){
        return add(x - y, _modulo);
    }

    int bpow(int x, int y){
        int res = 1;
        while(y){
            if(y&1) res = mul(res, x);

            x = mul(x, x);
            y >>= 1;
        }
        return res;
    }

    // Only if modulo is prime number
    int inv(int x){
        return bpow(x, _modulo - 2);
    }
}

using namespace modulo_function;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 1e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;

struct Node{
    int Mx,ways;
    Node(int Mx = 0, int ways = 0): Mx(Mx), ways(ways) {}

    Node operator + (const Node& q) const{
        if(Mx == q.Mx) return Node(Mx, add(ways, q.ways));

        return (Mx > q.Mx ? Node(Mx, ways) : q);
    }

    bool operator == (const Node& q) const{
        return Mx == q.Mx && ways == q.ways;
    }
};

struct SMT_MAX{
    int trsz;
    vector<Node> st;
    SMT_MAX(int n): trsz(n), st((n << 2 | 1)) {}

    void update(int id, int l, int r, int k, Node val){
        if(l == r){
            st[id] = val;
            return;
        }
        else{
            int m = l+r>>1;
            if(k <= m) update(id<<1, l, m, k, val);
            else{
                update(id<<1|1, m+1, r, k, val);
            }
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
        return;
    }

    Node get(int id, int l, int r, int u, int v){
        if(l > v || r < u) return Node();
        if(l >= u && r <= v) return st[id];

        int m = l+r>>1;
        return get(id << 1, l, m, u, v) + get(id << 1 | 1, m+1, r, u, v);
    }

    void update(int k, Node val){
        return update(1, 1, trsz, k, val), void();
    }

    Node get(int l, int r){
        return get(1, 1, trsz, l, r);
    }
};

struct Trapezoid{
    int a, b, c, d;

    Trapezoid(int _a = 0, int _b = 0, int _c = 0, int _d = 0){
        a = _a,
        b = _b,
        c = _c,
        d = _d;
    }

    friend istream& operator >> (istream &inp, Trapezoid& i){
        return inp >> i.a >> i.b >> i.c >> i.d, inp;
    }
};


Trapezoid trapezoid[N];

vector<int> compress;


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

    for(int i = 1; i <= n; i++){
        cin >> trapezoid[i];
        compress.push_back(trapezoid[i].a);
        compress.push_back(trapezoid[i].b);
    }

    sort(all(compress)), compact(compress);

    for(int i = 1; i <= n; i++){
        trapezoid[i].a = lower_bound(all(compress), trapezoid[i].a) - compress.begin() +1;
        trapezoid[i].b = lower_bound(all(compress), trapezoid[i].b) - compress.begin() +1;
    }

    vector<pair<int,int>> Point;

    for(int i = 1; i <= n; i++){
        Point.push_back(make_pair(trapezoid[i].c, i));
        Point.push_back(make_pair(trapezoid[i].d, -i));
    }

    SMT_MAX st(2 * n);

    vector<Node> save(n + 1);

    sort(all(Point));


    Node Mx = Node();
    for(int i = 0; i < sz(Point); i++){
        int id = Point[i].se;
        //cout << dbg(abs(id)) << dbg(Point[i].first) <<"\n";
        if(id > 0){
            Node value = st.get(1, trapezoid[id].a);
            if(value == Node()){
                save[id] = Node(1, 1);
            }
            else save[id] = value, save[id].Mx += 1;

            //cout << dbg(save[id].Mx) <<" " << dbg(save[id].ways) <<"\n";
            Mx = Mx + save[id];
        }
        else{
            id = -id;
            st.update(trapezoid[id].b, save[id]);
        }
    }

    cout << Mx.Mx <<" " << Mx.ways <<"\n";
}

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

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

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100