QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#285334#6633. Exam RequirementsMisukiML 1ms3516kbC++207.0kb2023-12-16 17:57:502023-12-16 17:57:51

Judging History

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

  • [2023-12-16 17:57:51]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3516kb
  • [2023-12-16 17:57:50]
  • 提交

answer

#pragma GCC optimize("O2")
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <compare>
#include <complex>
#include <concepts>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numbers>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <span>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>

//#define int ll
#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)
#define INT128_MIN (-INT128_MAX - 1)

namespace R = std::ranges;
namespace V = std::views;

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = tuple<int, int, int>;
using ldb = long double;
//#define double ldb

template<class T>
ostream& operator<<(ostream& os, const pair<T, T> pr) {
  return os << pr.first << ' ' << pr.second;
}
template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &arr) {
  for(const T &X : arr)
    os << X << ' ';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &vec) {
  for(const T &X : vec)
    os << X << ' ';
  return os;
}

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef vector<int> vi;

/**
 * Author: Emil Lenngren, Simon Lindholm
 * Date: 2011-11-29
 * License: CC0
 * Source: folklore
 * Description: Calculates a valid assignment to boolean variables a, b, c,... to a 2-SAT problem, so that an expression of the type $(a\|\|b)\&\&(!a\|\|c)\&\&(d\|\|!b)\&\&...$ becomes true, or reports that it is unsatisfiable.
 * Negated variables are represented by bit-inversions (\texttt{\tilde{}x}).
 * Usage:
 *  TwoSat ts(number of boolean variables);
 *  ts.either(0, \tilde3); // Var 0 is true or var 3 is false
 *  ts.setValue(2); // Var 2 is true
 *  ts.atMostOne({0,\tilde1,2}); // <= 1 of vars 0, \tilde1 and 2 are true
 *  ts.solve(); // Returns true iff it is solvable
 *  ts.values[0..N-1] holds the assigned values to the vars
 * Time: O(N+E), where N is the number of boolean variables, and E is the number of clauses.
 * Status: stress-tested
 */

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()

struct TwoSat {
	int N;
	vector<vi> gr;
	vi values; // 0 = false, 1 = true

	TwoSat(int n = 0) : N(n), gr(2*n) {}

	int addVar() { // (optional)
		//gr.emplace_back();
		//gr.emplace_back();
		return N++;
	}

	void either(int f, int j) {
		f = max(2*f, -1-2*f);
		j = max(2*j, -1-2*j);
		gr[f].push_back(j^1);
		gr[j].push_back(f^1);
	}
	void setValue(int x) { either(x, x); }

	void atMostOne(const vi& li) { // (optional)
		if (sz(li) <= 1) return;
		int cur = ~li[0];
		rep(i,2,sz(li)) {
			int next = addVar();
			either(cur, ~li[i]);
			either(cur, next);
			either(~li[i], next);
			cur = ~next;
		}
		either(cur, ~li[1]);
	}

	vi val, comp, z; int time = 0;
	int dfs(int i) {
		int low = val[i] = ++time, x; z.push_back(i);
		for(int e : gr[i]) if (!comp[e])
			low = min(low, val[e] ?: dfs(e));
		if (low == val[i]) do {
			x = z.back(); z.pop_back();
			comp[x] = low;
			if (values[x>>1] == -1)
				values[x>>1] = x&1;
		} while (x != i);
		return val[i] = low;
	}

	bool solve() {
		values.assign(N, -1);
		val.assign(2*N, 0); comp = val;
		rep(i,0,2*N) if (!comp[i]) dfs(i);
		rep(i,0,N) if (comp[2*i] == comp[2*i+1]) return 0;
		return 1;
	}
};

signed main() {
  ios::sync_with_stdio(false), cin.tie(NULL);

  int t; cin >> t;
  while(t--) {
    int n, m; cin >> n >> m;
    vector<array<int, 2>> lr(n), cond(m);
    for(auto &[l, r] : lr)
      cin >> l >> r;
    for(auto &[x, y] : cond) {
      cin >> x >> y;
      x--, y--;
    }

    {
      vector<int> tmp;
      for(auto [l, r] : lr) {
        tmp.emplace_back(l);
        tmp.emplace_back(r);
      }
      R::sort(tmp);
      tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
      for(auto &[l, r] : lr) {
        l = R::lower_bound(tmp, l) - tmp.begin();
        r = R::lower_bound(tmp, r) - tmp.begin();
      }
    }

    const int C = bit_ceil((unsigned)(n << 1));
    vector<vector<int>> seg(C << 1);
    auto query = [&](int l, int r) {
      vector<int> res;
      for(l += C, r += C; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res.emplace_back(l++);
        if (r & 1) res.emplace_back(--r);
      }
      return res;
    };

    int fakeN = n + 2 * C;
    vector<int> ssz(2 * fakeN);
    { //precalc size
      auto fakeAddVar = [&]() {
        ssz.emplace_back();
        ssz.emplace_back();
        return fakeN++;
      };
      auto fakeEither = [&](int f, int j) {
        f = max(2*f, -1-2*f);
        j = max(2*j, -1-2*j);
        ssz[f]++;
        ssz[j]++;
      };
      auto fakeAtMostOne = [&](const vi& li) {
        if (sz(li) <= 1) return;
        int cur = ~li[0];
        rep(i,2,sz(li)) {
          int next = fakeAddVar();
          fakeEither(cur, ~li[i]);
          fakeEither(cur, next);
          fakeEither(~li[i], next);
          cur = ~next;
        }
        fakeEither(cur, ~li[1]);
      };

      for(auto [x, y] : cond)
        fakeEither(x, y);
      for(int i = C; i < 2 * C; i++) {
        vector<int> path;
        int now = i;
        while(now) {
          path.emplace_back(now + n);
          now >>= 1;
        }
        fakeAtMostOne(path);
      }
      for(int i = 0; auto [l, r] : lr) {
        for(int x : query(l, r + 1))
          seg[x].emplace_back(i);
        i++;
      }
      for(int i = 1; i < 2 * C; i++) {
        if (!seg[i].empty())
          fakeAtMostOne(seg[i]);
        for(int x : seg[i])
          fakeEither(~x, i + n);
      }
    }

    TwoSat ts(n + 2 * C);
    ts.gr.resize(ssize(ssz));
    for(int i = 0; i < ssize(ssz); i++)
      ts.gr[i].reserve(ssz[i]);

    for(auto [x, y] : cond)
      ts.either(x, y);
    for(int i = C; i < 2 * C; i++) {
      vector<int> path;
      int now = i;
      while(now) {
        path.emplace_back(now + n);
        now >>= 1;
      }
      ts.atMostOne(path);
    }
    for(int i = 1; i < 2 * C; i++) {
      if (!seg[i].empty())
        ts.atMostOne(seg[i]);
      for(int x : seg[i])
        ts.either(~x, i + n);
    }

    cout << (ts.solve() ? "YES\n" : "NO\n");
  }

  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3516kb

input:

2
3 1
1 5
2 7
10 11
2 1
3 3
1 5
2 7
5 7
1 2
2 3
3 1

output:

YES
NO

result:

ok 2 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

1
100000 100000
15084647 15220430
217541056 217598054
222963701 223110976
71224450 71340221
320463268 320631387
334861459 334924668
328950591 329083669
178996498 178996584
428529461 428605033
405428435 405504132
197936687 197947412
9058562 9190197
169407597 169474101
297518153 297590927
31471874 316...

output:

NO

result: