Submission #1223325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223325		Sunbae	trapezoid (balkan11_trapezoid)	C++20	100 / 100	81 ms	7240 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, dN = 2e5 + 5, mod = 30013;
pair<int,int> dp[N], bit[dN];
int s1[N], e1[N], s2[N], e2[N], is1[dN], ie1[dN], cp1[dN], cp2[dN], m1, m2, mx, c;
int p1(int x){ return upper_bound(cp1, cp1+m1, x) - cp1;}
int p2(int x){ return upper_bound(cp2, cp2+m2, x) - cp2;}
void upd(int i, pair<int,int> v){
    for(; i<=m2; i+=i&-i){
        if(v.first > bit[i].first) bit[i] = v;
        else if(v.first == bit[i].first) bit[i].second = (bit[i].second + v.second) % mod;
    }
}
pair<int,int> qry(int i){
    pair<int,int> r = {0, 0};
    for(; i; i-=i&-i){
        if(bit[i].first > r.first) r = bit[i];
        else if(bit[i].first == r.first) r.second = (r.second + bit[i].second) % mod;
    }
    return r;
}
signed main(){
    int n; scanf("%d", &n);
    for(int i = cp2[m2++] = 0; i<n; ++i){
        scanf("%d %d %d %d", s1+i, e1+i, s2+i, e2+i);
        cp1[m1++] = s1[i]; cp1[m1++] = e1[i];
        cp2[m2++] = s2[i]; cp2[m2++] = e2[i];
    }
    sort(cp1, cp1+m1); m1 = unique(cp1, cp1+m1) - cp1;
    sort(cp2, cp2+m2); m2 = unique(cp2, cp2+m2) - cp2;
    memset(is1, -1, sizeof(is1)); memset(ie1, -1, sizeof(ie1));
    for(int i = 0; i<n; ++i){
        s1[i] = p1(s1[i]); e1[i] = p1(e1[i]);
        s2[i] = p2(s2[i]); e2[i] = p2(e2[i]);
        is1[s1[i]] = ie1[e1[i]] = i;
    }
    upd(p2(0), {0, 1});
    for(int x = 1, i; x<=m1; ++x){
        if(~(i = is1[x])){
            dp[i] = qry(s2[i]); 
            mx = max(mx, ++dp[i].first);
        }
        if(~(i = ie1[x])) upd(e2[i], dp[i]);
    }
    for(int i = 0; i<n; ++i) if(dp[i].first == mx) c = (c + dp[i].second) % mod;
    printf("%d %d\n", mx, c);
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:23:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     int n; scanf("%d", &n);
      |            ~~~~~^~~~~~~~~~
trapezoid.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d %d %d %d", s1+i, e1+i, s2+i, e2+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100