Submission #1376279


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

template< class T >
struct BinaryIndexedTree
{
  vector< T > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  T sum(int k)
  {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};


int main()
{
  int R, C, N;
  cin >> R >> C >> N;

  vector< pair< int, int > > row;
  vector< int > ss;
  for(int i = 0; i < N; i++) {
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    bool iskabe1 = a == 0 || a == R || b == 0 || b == C;
    bool iskabe2 = c == 0 || c == R || d == 0 || d == C;

    auto get = [&](int x, int y)
    {
      if(x == 0) return (y);
      if(y == C) return (C + x);
      if(x == R) return (C + R + (C - y));
      return (C + R + C + (R - x));
    };

    if(iskabe1 && iskabe2) {
      int s = get(a, b), t = get(c, d);
      if(s > t) swap(s, t);

      ss.push_back(s);
      ss.push_back(t);
      ss.push_back(t + 1);
      row.emplace_back(s, t);
    }
  }


  sort(begin(ss), end(ss));
  ss.erase(unique(begin(ss), end(ss)), end(ss));
  BinaryIndexedTree< int > bit(ss.size());

  for(auto &p : row) {
    p.first = lower_bound(begin(ss), end(ss), p.first) - begin(ss);
    p.second = lower_bound(begin(ss), end(ss), p.second) - begin(ss);
    bit.add(p.first, 1);
    bit.add(p.second + 1, -1);
  }
  for(auto &p : row) {
    if(bit.sum(p.first) != bit.sum(p.second)) {
      cout << "NO" << endl;
      return (0);
    }
  }
  cout << "YES" << endl;

}

Submission Info

Submission Time
Task E - Connected?
User ei13333
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1659 Byte
Status
Exec Time 182 ms
Memory 3560 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 700 / 700 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 43.txt, 44.txt, 45.txt, 46.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 154 ms 2540 KB
02.txt 157 ms 2160 KB
03.txt 162 ms 2288 KB
04.txt 141 ms 768 KB
05.txt 160 ms 2160 KB
06.txt 182 ms 3432 KB
07.txt 144 ms 640 KB
08.txt 160 ms 2416 KB
09.txt 151 ms 1652 KB
10.txt 170 ms 3052 KB
11.txt 161 ms 2668 KB
12.txt 137 ms 256 KB
13.txt 141 ms 768 KB
14.txt 142 ms 1780 KB
15.txt 149 ms 1780 KB
16.txt 141 ms 384 KB
17.txt 143 ms 256 KB
18.txt 137 ms 256 KB
19.txt 144 ms 1148 KB
20.txt 173 ms 3432 KB
21.txt 150 ms 1524 KB
22.txt 151 ms 1780 KB
23.txt 177 ms 3560 KB
24.txt 177 ms 3560 KB
25.txt 179 ms 3560 KB
26.txt 180 ms 3560 KB
27.txt 178 ms 3560 KB
28.txt 170 ms 3560 KB
29.txt 177 ms 3560 KB
30.txt 178 ms 3560 KB
43.txt 1 ms 256 KB
44.txt 1 ms 256 KB
45.txt 1 ms 256 KB
46.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB
s4.txt 1 ms 256 KB