oj.uz

Submission #526828

# Submission time Handle Problem Language Result Execution time Memory
526828 2022-02-16T08:26:07 Z BackNoob trapezoid (balkan11_trapezoid) C++14
0 / 100
 119 ms 10332 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct item
{
    int x, y, u, v;
} a[mxN];

struct seg
{
    int l, r, ok , idx;
    bool operator<(seg a)
    {
        if(l == a.l && r == a.r) return ok > a.ok;
        if(l == a.l) return r < a.r;
        return l < a.l;
    }
};

int n;
int f[mxN];
int g[mxN];

void add(int &a , int b)
{
    a += b;
    if(a >= mod) a -= mod;
}

int bitadd[mxN * 2];
void updateadd(int pos, int val)
{
    for(; pos <= 2 * n ; pos += pos & -pos) add(bitadd[pos] , val);
}
int getsum(int pos)
{
    int res = 0;
    for(; pos > 0 ; pos -= pos & -pos) add(res , bitadd[pos]);
    return res;
}

int getsum(int l , int r)
{
    int res = getsum(r) - getsum(l - 1);
    if(res < 0) res += mod;
}

int bitmax[mxN * 2];
void updatemax(int pos, int val)
{
    for(; pos <= n * 2 ; pos += pos & -pos) maximize(bitmax[pos] , val);
}
int getmax(int pos)
{
    int res = 0;
    for(; pos > 0 ; pos -= pos & -pos) maximize(res , bitmax[pos]);
    return res;
}

vector<int> cpx , cpy;

void solve()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
        cpx.pb(a[i].x);
        cpy.pb(a[i].y);
        cpx.pb(a[i].u);
        cpy.pb(a[i].v);
    }

    sort(all(cpx));
    cpx.erase(unique(all(cpx)) , cpx.end());
    sort(all(cpy));
    cpy.erase(unique(all(cpy)) , cpy.end());

    for(int i = 1 ; i <= n ; i++) {
        a[i].x = lower_bound(all(cpx) , a[i].x) - cpx.begin() + 1;
        a[i].y = lower_bound(all(cpy) , a[i].y) - cpy.begin() + 1;
        a[i].u = lower_bound(all(cpx) , a[i].u) - cpx.begin() + 1;
        a[i].v = lower_bound(all(cpy) , a[i].v) - cpy.begin() + 1;
    }

    vector<seg> val;
    for(int i = 1 ; i <= n ; i++)
    {
        val.pb({a[i].x , a[i].y , 1 , i});
        val.pb({a[i].u , a[i].v , 0 , i});
    }
    sort(all(val));

    for(auto it : val)
    {
        int i = it.idx;
        if(it.ok == 0) {
            //cout << it.r << ' ' << f[i] << ' ' << g[i] << endl;
            updatemax(it.r , f[i]);
            updateadd(f[i] , g[i]);
        }
        else {
            f[i] = max(1 , getmax(it.r) + 1);
            if(f[i] == 1) g[i] = 1;
            else g[i] = getsum(f[i] - 1 , f[i] - 1);
        }
    }

    int res = getmax(2 * n);
    int ans = getsum(res , res);
    cout << res << ' ' << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

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

Compilation message

trapezoid.cpp: In function 'int getsum(int, int)':
trapezoid.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
   72 | }
      | ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 584 KB Execution killed with signal 11
2 Runtime error 3 ms 580 KB Execution killed with signal 11
3 Runtime error 3 ms 712 KB Execution killed with signal 11
4 Runtime error 4 ms 716 KB Execution killed with signal 11
5 Runtime error 4 ms 976 KB Execution killed with signal 11
6 Runtime error 5 ms 1040 KB Execution killed with signal 11
7 Runtime error 6 ms 1088 KB Execution killed with signal 11
8 Runtime error 9 ms 1288 KB Execution killed with signal 11
9 Runtime error 12 ms 1804 KB Execution killed with signal 11
10 Runtime error 23 ms 2920 KB Execution killed with signal 11
11 Runtime error 29 ms 3324 KB Execution killed with signal 11
12 Runtime error 57 ms 5436 KB Execution killed with signal 11
13 Runtime error 68 ms 6352 KB Execution killed with signal 11
14 Runtime error 81 ms 8724 KB Execution killed with signal 11
15 Runtime error 90 ms 8948 KB Execution killed with signal 11
16 Runtime error 97 ms 9152 KB Execution killed with signal 11
17 Runtime error 96 ms 9524 KB Execution killed with signal 11
18 Runtime error 97 ms 9824 KB Execution killed with signal 11
19 Runtime error 111 ms 10016 KB Execution killed with signal 11
20 Runtime error 119 ms 10332 KB Execution killed with signal 11