Submission #376793

#	Time	Username	Problem	Language	Result	Execution time	Memory
376793		couplefire	trapezoid (balkan11_trapezoid)	C++17	100 / 100	395 ms	57260 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 524288
#define MOD 30013

inline int add(int a, int b){return (a+b>=MOD)?a+b-MOD:a+b;}
inline void inc(int& a, int b){a = add(a, b);}
inline int sub(int a, int b){return (a-b<0)?a-b+MOD:a-b;}
inline void dec(int &a, int b){a = sub(a, b);}
inline int mul(int a, int b){return 1ll*a*b%MOD;}
inline void grow(int &a, int b){a = mul(a, b);}

pair<int, int> tree[2*INF];

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    if(a.first != b.first) return max(a, b);
    return {a.first, add(a.second,b.second)};
}

void upd(int pos, int val, int cnt, int tl = 0, int tr = INF-1, int v = 1){
    if(tl > pos || tr < pos) return;
    if(tl == tr){
        tree[v] = {val, cnt};
        return;
    }
    int tm = (tl+tr)/2;
    upd(pos, val, cnt, tl, tm, v*2);
    upd(pos, val, cnt, tm+1, tr, v*2+1);
    tree[v] = merge(tree[v*2], tree[v*2+1]);
}

pair<int, int> query(int l, int r, int tl = 0, int tr = INF-1, int v = 1){
    if(tl > r || tr < l) return {0, 0};
    if(l <= tl && tr <= r) return tree[v];
    int tm = (tl+tr)/2;
    return merge(query(l, r, tl, tm, v*2), query(l, r, tm+1, tr, v*2+1));
}

int n;
vector<int> coords;
map<int, int> mp;
pair<pair<int, int>, pair<int, int>> stuff[MAXN];
vector<pair<int, int>> ask[INF]; // y-coord, id
vector<pair<pair<int, int>, int>> todo[INF]; // val, y-coord
pair<int, int> ans = {0, 1};

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i<=n; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        coords.push_back(a); coords.push_back(b); coords.push_back(c); coords.push_back(d);
        stuff[i] = {{a, c}, {b, d}};
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    // for(auto x : coords) cout << x << endl;
    for(int i = 0; i<coords.size(); i++) mp[coords[i]] = i+1;
    for(int i = 1; i<=n; i++) stuff[i] = {{mp[stuff[i].first.first], mp[stuff[i].first.second]}, {mp[stuff[i].second.first], mp[stuff[i].second.second]}};
    for(int i = 1; i<=n; i++) ask[stuff[i].first.first].push_back({stuff[i].first.second, i});
    for(int i = 1; i<INF; i++){
        for(auto x : ask[i]){
            pair<int, int> tmp = query(0, x.first-1); tmp.first += 1; if(tmp.first == 1) tmp.second = 1;
            ans = merge(ans, tmp);
            todo[stuff[x.second].second.first].push_back({tmp, stuff[x.second].second.second});
        }
        for(auto x : todo[i]){
            upd(x.second, x.first.first, x.first.second);
        }
    }
    cout << ans.first << endl;
    cout << ans.second << endl;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100