oj.uz

Submission #526831

# Submission time Handle Problem Language Result Execution time Memory
526831 2022-02-16T08:32:52 Z BackNoob trapezoid (balkan11_trapezoid) C++14
0 / 100
 112 ms 7892 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;
}

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;
            if(f[i] == 0) {
                cout << "f";
                exit(0);
            }
            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:71:1: warning: no return statement in function returning non-void [-Wreturn-type]
   71 | }
      | ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Expected integer, but "f" found
2 Incorrect 1 ms 332 KB Expected integer, but "f" found
3 Incorrect 1 ms 332 KB Expected integer, but "f" found
4 Incorrect 1 ms 460 KB Expected integer, but "f" found
5 Incorrect 2 ms 588 KB Expected integer, but "f" found
6 Incorrect 3 ms 716 KB Expected integer, but "f" found
7 Incorrect 4 ms 844 KB Expected integer, but "f" found
8 Incorrect 6 ms 972 KB Expected integer, but "f" found
9 Incorrect 11 ms 1424 KB Expected integer, but "f" found
10 Incorrect 19 ms 2336 KB Expected integer, but "f" found
11 Incorrect 27 ms 2516 KB Expected integer, but "f" found
12 Incorrect 54 ms 4136 KB Expected integer, but "f" found
13 Incorrect 62 ms 4584 KB Expected integer, but "f" found
14 Incorrect 75 ms 6904 KB Expected integer, but "f" found
15 Incorrect 92 ms 7256 KB Expected integer, but "f" found
16 Incorrect 90 ms 7252 KB Expected integer, but "f" found
17 Incorrect 91 ms 7464 KB Expected integer, but "f" found
18 Incorrect 92 ms 7528 KB Expected integer, but "f" found
19 Incorrect 99 ms 7732 KB Expected integer, but "f" found
20 Incorrect 112 ms 7892 KB Expected integer, but "f" found