제출 #668333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668333		Ninja_Kunai	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	140 ms	41508 KiB

trapezoid

/**
*    Author :  Nguyen Tuan Vu
*    Created : 03.12.2022
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

void file(){
    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}

const int N = 1e5 + 5;
const int Mod = 30013;
int n;
pair <int, int> res[N];

struct RECTANGLE {
	int a, b, c, d;
} a[N];

struct LINE {
	int up, down, id, type;

	LINE() {}
	LINE(int up, int down, int id, int type) {
		this->up = up;
		this->down = down;
		this->id = id;
		this->type = type;
	}

	friend bool operator < (LINE &x, LINE &y) {
		if (x.up != y.up) return x.up < y.up;
		if (x.id != y.id) return x.type < y.type;
		return x.type > y.type;
	}
};

vector <LINE> line;

void add(int &x, int K) {
	x += K;
	if (x >= Mod) x -= Mod;
}

struct Fenwick_Tree {
	int n;
	vector <pair <int, int>> bit;

	Fenwick_Tree(int n) {
		this->n = n;
		bit.resize(n + 7, make_pair(0, 0));
	}

	void update(int u, pair <int, int> val) {
		for (; u <= n; u += u & -u) if (bit[u].first < val.first) {
			bit[u] = val;
		}
		else if (bit[u].first == val.first) {
			add(bit[u].second, val.second);
		}
	}

	pair <int, int> get(int u) {
		pair <int, int> ans = make_pair(0, 0);
		for (; u; u -= u & -u) if (ans.first < bit[u].first) ans = bit[u];
			else if (ans.first == bit[u].first) add(ans.second, bit[u].second);
		return ans;
	}
};

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();
    cin >> n;
    vector <int> ctz;
    FOR(i, 0, n) {
    	if (i > 0) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
    	ctz.push_back(a[i].a);
    	ctz.push_back(a[i].b);
    	ctz.push_back(a[i].c);
    	ctz.push_back(a[i].d);
    }

    sort (ALL(ctz));
    ctz.erase(unique(ALL(ctz)), ctz.end());

    FOR(i, 1, n) {
    	a[i].a = lower_bound(ALL(ctz), a[i].a) - ctz.begin() + 1;
    	a[i].b = lower_bound(ALL(ctz), a[i].b) - ctz.begin() + 1;
    	a[i].c = lower_bound(ALL(ctz), a[i].c) - ctz.begin() + 1;
    	a[i].d = lower_bound(ALL(ctz), a[i].d) - ctz.begin() + 1;

    	line.push_back(LINE(a[i].a, a[i].c, i, 1));
    	line.push_back(LINE(a[i].b, a[i].d, i, -1));
    }

  	//FOR(i, 1, n) {
  	//	cout << a[i].a << ' ' << a[i].b << ' ' << a[i].c << ' ' << a[i].d << '\n';
  	//}

    sort (ALL(line));
    Fenwick_Tree mybit(4e6);
    mybit.update(lower_bound(ALL(ctz), 0) - ctz.begin() + 1, make_pair(0, 1));

    for (auto x : line) {
    	if (x.type == -1) {
    		mybit.update(a[x.id].d, res[x.id]);
    	}
    	else {
    		res[x.id] = mybit.get(a[x.id].c);
    		res[x.id].first++;
    	}
    }

    pair <int, int> ans = make_pair(0, 1);
    FOR(i, 1, n) if (ans.first < res[i].first) {
    	ans = res[i];
    }
    else if (ans.first == res[i].first) add(ans.second, res[i].second);
    cout << ans.first << ' ' << ans.second << '\n';
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

컴파일 시 표준 에러 (stderr) 메시지

trapezoid.cpp: In function 'void file()':
trapezoid.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100