QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#427333#8780. Training, Round 2ucup-team3099#WA 4ms17936kbC++205.3kb2024-06-01 12:47:062024-06-01 12:47:06

Judging History

你现在查看的是最新测评结果

  • [2024-06-01 12:47:06]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:17936kb
  • [2024-06-01 12:47:06]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG 1
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

#if 0
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
 
    template<class T>
    using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag,
        __gnu_pbds::tree_order_statistics_node_update>;
#endif

#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <queue>
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <ctime> 
#include <cstring>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)

#define each(a,x) for (auto& a: x)
#define tcT template<class T
#define tcTU tcT, class U
#define tcTUU tcT, class ...U
template<class T> using V = vector<T>; 
template<class T, size_t SZ> using AR = array<T,SZ>;

typedef string str;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }
 
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
 
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(vector<bool> v) { str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) { str res = ""; F0R(i,SZ) res += char('0'+b[i]); return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { bool fst = 1; str res = "{"; for (const auto& x: v) {if (!fst) res += ", ";	fst = 0; res += ts(x);}	res += "}"; return res;}
template<class A, class B> str ts(pair<A,B> p) {return "("+ts(p.first)+", "+ts(p.second)+")"; }
 
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { pr(h); pr(t...); }
void ps() { pr("\n"); }
template<class H, class... T> void ps(const H& h, const T&... t) { pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {cerr << ts(h); if (sizeof...(t)) cerr << ", ";	DBG(t...); }

tcTU> void re(pair<T,U>& p);
tcT> void re(V<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);

tcT> void re(T& x) { cin >> x; }
void re(double& d) { str t; re(t); d = stod(t); }
void re(long double& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }

tcTU> void re(pair<T,U>& p) { re(p.first,p.second); }
tcT> void re(V<T>& x) { each(a,x) re(a); }
tcT, size_t SZ> void re(AR<T,SZ>& x) { each(a,x) re(a); }
tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); }

constexpr bool multitest() {return 0;}
void solve();
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t = 1;
	if (multitest()) cin >> t;
	for (; t; t--) solve();
}






















int tree[5010][5010];

int get(int ox, int oy) {
	int s = 0;
	for (int x = ox+1; x > 0; x-=x&-x) {
		for (int y = oy+1; y > 0; y-=y&-y) {
			s += tree[x][y];
		}
	}
	return s;
}

int getr(int x1, int x2, int y1, int y2) {
	return get(x2,y2) - get(x1-1,y2) - get(x2,y1-1) + get(x1-1,y1-1);
}

void add(int ox, int oy, int d) {
	for (int x = ox+1; x < 5010; x+=x&-x) {
		for (int y = oy+1; y < 5010; y+=y&-y) {
			tree[x][y] += d;
		}
	}
}

vector<pii> to_process;

void get_points(int sx, int bx, int sy, int by, int tot) {
	if (tot == 0) return;

	if (sx == bx && sy == by) {
		to_process.push_back({sx,sy});
		return;
	}

	if (sx != bx) {
		int m = (sx+bx)/2;
		int mr = getr(sx,m,sy,by);
		get_points(sx, m, sy, by, mr);
		get_points(m+1, bx, sy, by, tot-mr);
		return;
	}

	int m = (sy+by)/2;
	int mr = getr(sx,bx,sy,m);
	get_points(sx,bx,sy,m,mr);
	get_points(sx,bx,m+1,by,tot-mr);
}

int seen[5010][5010];

void solve() {
	int n, si, sst; re(n,si,sst);

	seen[0][0] = 1;
	add(0, 0, 1);

	int ans = 0;

	for (int i = 0; i < n; i++) {
		int il, ih, tl, th; re(il, ih, tl, th);
		il -= si;
		ih -= si;
		tl -= sst;
		th -= sst;

		il = max(0, min(il, 5008));
		ih = min(ih, 5008);
		tl = max(0, min(tl, 5008));
		th = min(th, 5008);
		
		if (il > ih || tl > th) continue;

		to_process.clear();
		get_points(il,ih,tl,th,getr(il,th,tl,th));

		for (auto [x, y]: to_process) {
			ans = max(ans, x+y+1);
			add(x,y,-1);

			if (!seen[x+1][y]) {
				seen[x+1][y] = 1;
				add(x+1,y,1);
			}
			if (!seen[x][y+1]) {
				seen[x][y+1] = 1;
				add(x,y+1,1);
			}
		}
	}

	ps(ans);
}


















































	







Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 17936kb

input:

3 0 0
0 1 0 1
1 1 0 1
1 1 1 1

output:

3

result:

ok single line: '3'

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 17936kb

input:

5000 801577551 932138594
801577551 801577551 932138594 932138594
801577552 801577552 932138594 932138594
801577552 801577552 932138595 932138595
801577552 801577552 932138596 932138596
801577553 801577553 932138596 932138596
801577553 801577553 932138597 932138597
801577553 801577553 932138598 93213...

output:

1

result:

wrong answer 1st lines differ - expected: '5000', found: '1'