oj.uz

답안 #526843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526843 2022-02-16T09:09:44 Z BackNoob 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 122 ms 7644 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 = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 30013;
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;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(ll l , ll r) {
    return l + rd() * 1LL * rd() % (r - l + 1);
}

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> valx , valy;

void solve()
{
//    n = Rand(2 , 3);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
//        a[i].x = Rand(1 , 10);
//        a[i].y = Rand(1 , 10);
//        a[i].u = Rand(a[i].x , 20);
//        a[i].v = Rand(a[i].y , 20);
        valx.pb(a[i].x);
        valy.pb(a[i].y);
        valx.pb(a[i].u);
        valy.pb(a[i].v);
    }

    //cout << n << endl;
    //for(int i = 1 ; i <= n ; i++)
    //    cout << a[i].x << ' ' << a[i].u << ' ' << a[i].y << ' ' << a[i].v << endl;

    sort(all(valx));
    valx.erase(unique(all(valx)) , valx.end());
    sort(all(valy));
    valy.erase(unique(all(valy)) , valy.end());

    for(int i = 1 ; i <= n ; i++) {
        a[i].x = lower_bound(all(valx) , a[i].x) - valx.begin() + 1;
        a[i].y = lower_bound(all(valy) , a[i].y) - valy.begin() + 1;
        a[i].u = lower_bound(all(valx) , a[i].u) - valx.begin() + 1;
        a[i].v = lower_bound(all(valy) , a[i].v) - valy.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) + 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:77:1: warning: no return statement in function returning non-void [-Wreturn-type]
   77 | }
      | ^

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 11
2 Runtime error 3 ms 588 KB Execution killed with signal 11
3 Runtime error 5 ms 588 KB Execution killed with signal 11
4 Runtime error 3 ms 716 KB Execution killed with signal 11
5 Runtime error 6 ms 844 KB Execution killed with signal 11
6 Runtime error 6 ms 996 KB Execution killed with signal 11
7 Runtime error 6 ms 992 KB Execution killed with signal 11
8 Runtime error 9 ms 1192 KB Execution killed with signal 11
9 Runtime error 12 ms 1620 KB Execution killed with signal 11
10 Runtime error 22 ms 2380 KB Execution killed with signal 11
11 Runtime error 27 ms 2756 KB Execution killed with signal 11
12 Runtime error 63 ms 4036 KB Execution killed with signal 11
13 Runtime error 73 ms 4712 KB Execution killed with signal 11
14 Runtime error 81 ms 6704 KB Execution killed with signal 11
15 Runtime error 86 ms 6856 KB Execution killed with signal 11
16 Runtime error 94 ms 7016 KB Execution killed with signal 11
17 Runtime error 95 ms 7176 KB Execution killed with signal 11
18 Runtime error 100 ms 7412 KB Execution killed with signal 11
19 Runtime error 107 ms 7476 KB Execution killed with signal 11
20 Runtime error 122 ms 7644 KB Execution killed with signal 11