Submission #1376131


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;

  BinaryIndexedTree< int > bit(R + C + R + C + 1);
  vector< pair< int, int > > row;
  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);
      bit.add(s, 1);
      bit.add(t + 1, -1);
      row.emplace_back(s, t);
    }
  }

  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 0
Code Size 1307 Byte
Status
Exec Time 524 ms
Memory 1562752 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 0 / 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 165 ms 71288 KB
02.txt 248 ms 294652 KB
03.txt 412 ms 868476 KB
04.txt 309 ms 577536 KB
05.txt 469 ms 1065468 KB
06.txt 237 ms 247544 KB
07.txt 402 ms 904960 KB
08.txt 305 ms 528892 KB
09.txt 435 ms 1002236 KB
10.txt 401 ms 849400 KB
11.txt 281 ms 455800 KB
12.txt 224 ms 305152 KB
13.txt 340 ms 690560 KB
14.txt 162 ms 102908 KB
15.txt 210 ms 232444 KB
16.txt 390 ms 861568 KB
17.txt 384 ms 842112 KB
18.txt 269 ms 459008 KB
19.txt 457 ms 1097728 KB
20.txt 378 ms 768632 KB
21.txt 357 ms 720892 KB
22.txt 524 ms 1295484 KB
23.txt 483 ms 1118200 KB
24.txt 500 ms 1174392 KB
25.txt 325 ms 522360 KB
26.txt 375 ms 746232 KB
27.txt 348 ms 655992 KB
28.txt 176 ms 104824 KB
29.txt 400 ms 812920 KB
30.txt 322 ms 552696 KB
43.txt 1 ms 256 KB
44.txt 447 ms 1562752 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