제출 #586000

#제출 시각아이디문제언어결과실행 시간메모리
586000ParsaEs청소 (JOI20_sweeping)C++14
컴파일 에러
0 ms0 KiB
//InTheNameOfGOD //PRS;) #pragma GCC optimize("unroll-loops", "Ofast", "O3") #include<iostream> #include<algorithm> #define rep(i, l, r, x) for(ll i = l; i != r; i += x) #define max(x, y) (x > y ? x : y) #define mx(x, y) (x = max(x, y)) #define X first #define Y second typedef int ll; using namespace std; typedef pair<ll, ll> pl; ypedef pair<ll, pl> pi; constexpr ll xn = 1e6 + 5e5, xq = 1e6 + 5; ll m1[xn << 2], m2[xn << 2], z1[xn << 2], z2[xn << 2], in[xn], ax[xq], ay[xq], o[xq], o1[xq], gt, prs; pi q[xn], q1[xn]; void bld(ll v, ll l, ll r, ll l1, ll r1) { if(r <= l1 || r1 <= l) return; m1[v] = m2[v] = z1[v] = z2[v] = -1; if(r - l < 2) return; ll m = l + r >> 1; bld(v << 1, l, m, l1, r1), bld(v << 1 | 1, m, r, l1, r1); } inline void p1(ll v) { ll x = m1[v << 1], y = m1[v << 1 | 1]; if(x >= 0) mx(q[x].Y.X, z1[v]), mx(z1[v << 1], z1[v]); if(y >= 0) mx(q[y].Y.X, z1[v]), mx(z1[v << 1 | 1], z1[v]); z1[v] = -1; } inline void p2(ll v) { ll x = m2[v << 1], y = m2[v << 1 | 1]; if(x >= 0) mx(q[x].Y.Y, z2[v]), mx(z2[v << 1], z2[v]); if(y >= 0) mx(q[y].Y.Y, z2[v]), mx(z2[v << 1 | 1], z2[v]); z2[v] = -1; } void g1(ll v, ll l, ll r, ll l1, ll r1) { if(r <= l1 || r1 <= l) return; if(l1 <= l && r <= r1) { if(m1[v] < 0) return; if(gt < 0 || q[m1[v]].Y.X < q[gt].Y.X) gt = m1[v]; return; } if(z1[v] >= 0) p1(v); ll m = l + r >> 1; g1(v << 1, l, m, l1, r1), g1(v << 1 | 1, m, r, l1, r1); } void g2(ll v, ll l, ll r, ll l1, ll r1) { if(r <= l1 || r1 <= l) return; if(l1 <= l && r <= r1) { if(m2[v] < 0) return; if(gt < 0 || q[m2[v]].Y.Y < q[gt].Y.Y) gt = m2[v]; return; } if(z2[v] >= 0) p2(v); ll m = l + r >> 1; g2(v << 1, l, m, l1, r1), g2(v << 1 | 1, m, r, l1, r1); } inline void d1(ll v) { ll x = m1[v << 1], y = m1[v << 1 | 1]; m1[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.X < q[y].Y.X ? x : y); } inline void d2(ll v) { ll x = m2[v << 1], y = m2[v << 1 | 1]; m2[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.Y < q[y].Y.Y ? x : y); } void pt1(ll v, ll l, ll r, ll x, bool f) { if(x < l || r <= x) return; if(r - l < 2) { m1[v] = -1; if(f) m1[v] = x; return; } if(z1[v] >= 0) p1(v); ll m = l + r >> 1; pt1(v << 1, l, m, x, f), pt1(v << 1 | 1, m, r, x, f), d1(v); } void pt2(ll v, ll l, ll r, ll x, bool f) { if(x < l || r <= x) return; if(r - l < 2) { m2[v] = -1; if(f) m2[v] = x; return; } if(z2[v] >= 0) p2(v); ll m = l + r >> 1; pt2(v << 1, l, m, x, f), pt2(v << 1 | 1, m, r, x, f), d2(v); } void up1(ll v, ll l, ll r, ll l1, ll r1, ll x) { if(r <= l1 || r1 <= l) return; if(l1 <= l && r <= r1) { ll y = m1[v]; if(y >= 0) mx(q[y].Y.X, x), mx(z1[v], x); return; } ll m = l + r >> 1; up1(v << 1, l, m, l1, r1, x), up1(v << 1 | 1, m, r, l1, r1, x); } void up2(ll v, ll l, ll r, ll l1, ll r1, ll x) { if(r <= l1 || r1 <= l) return; if(l1 <= l && r <= r1) { ll y = m2[v]; if(y >= 0) mx(q[y].Y.Y, x), mx(z2[v], x); return; } ll m = l + r >> 1; up2(v << 1, l, m, l1, r1, x), up2(v << 1 | 1, m, r, l1, r1, x); } void doj(ll l, ll r, ll d, ll x, ll y, ll n) { ll l1 = l, r1 = r; if(r1 < l1) swap(l1, r1), l1++, r1++; if(r1 <= l1) return; bld(1, 0, prs, l1, r1); ll a1 = l1, a2 = r1 - 1, r2 = 0, c2 = 0; if(n > 0) r2 = c2 = 1; if(n > 1) r2 = (n + 1) >> 1, c2 = n >> 1; rep(i, l, r, d) { if(o[i] == 1) { ll a = in[q[i].X], b = q[i].Y.X; if(a < -1) q1[a1] = q[i], o1[a1++] = 1; else if(a < 0) q1[a2] = q[i], o1[a2--] = 1; if(a >= 0) g1(1, 0, prs, a, a + 1), g2(1, 0, prs, a, a + 1); ax[b] = q[a].Y.X, ay[b] = q[a].Y.Y; } if(o[i] == 2) { ll a = q[i].X; if(r2 <= a) { if(r2 < a) q1[a2] = {a - r2, {0, 0}}, o1[a2--] = 2; up1(1, 0, prs, l1, r1, x + n - a); } else { q1[a1] = q[i], o1[a1++] = 2; while(1) { gt = -1, g2(1, 0, prs, l1, r1); if(gt < 0 || q[gt].Y.Y > y + a) break; pt1(1, 0, prs, gt, 0), pt2(1, 0, prs, gt, 0); pi p = q[gt]; q1[a1] = {p.X, {x - a + n, p.Y.Y}}, o1[a1++] = 4, in[p.X] = -2; } } } if(o[i] == 3) { ll a = q[i].X; if(c2 <= a) { if(c2 < a) q1[a1] = {a - c2, {0, 0}}, o1[a1++] = 3; up2(1, 0, prs, l1, r1, y + n - a); } else { q1[a2] = q[i], o1[a2--] = 3; while(1) { gt = -1, g1(1, 0, prs, l1, r1); if(gt < 0 || q[gt].Y.X > x + a) break; pt1(1, 0, prs, gt, 0), pt2(1, 0, prs, gt, 0); pi p = q[gt]; q1[a2] = {p.X, {p.Y.X, y - a + n}}, o1[a2--] = 4, in[p.X] = -1; } } } if(o[i] == 4) { pi p = q[i]; if(p.Y.X > x + c2) q1[a1] = p, in[p.X] = -2, o1[a1++] = 4; else if(p.Y.Y > y + r2) q1[a2] = p, in[p.X] = -1, o1[a2--] = 4; else pt1(1, 0, prs, i, 1), pt2(1, 0, prs, i, 1); } } rep(i, l, r, d) { q[i] = q1[i], o[i] = o1[i]; if(o[i] == 4) in[q[i].X] = i; } if(n < 2) doj(l1, a1, 1, x + 1, y, 0), doj(r1 - 1, a2, -1, x, y + 1, 0); else doj(l1, a1, 1, x + c2, y, r2), doj(r1 - 1, a2, -1, x, y + r2, c2); } int main() { ll n, m, Q; scanf("%d %d %d", &n, &m, &Q); rep(i, 0, m, 1) { ll x, y; scanf("%d %d", &x, &y), q[i] = {i, {x, y}}, in[i] = i, o[i] = 4; } ll cnt = m, ca = 0; rep(i, m, m + Q, 1) { scanf("%d", &o[i]); if(o[i] < 4) scanf("%d", &q[i].X); else scanf("%d %d", &q[i].Y.X, &q[i].Y.Y), in[cnt] = i, q[i].X = cnt++; if(o[i] == 1) q[i].X--, q[i].Y.X = ca++; } prs = m + Q, doj(0, prs, 1, 0, 0, n); rep(i, 0, ca, 1) printf("%d %d\n", ax[i], ay[i]); }

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

sweeping.cpp:14:1: error: 'ypedef' does not name a type
   14 | ypedef pair<ll, pl> pi;
      | ^~~~~~
sweeping.cpp:17:1: error: 'pi' does not name a type; did you mean 'pl'?
   17 | pi q[xn], q1[xn];
      | ^~
      | pl
sweeping.cpp: In function 'void bld(ll, ll, ll, ll, ll)':
sweeping.cpp:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void p1(ll)':
sweeping.cpp:29:19: error: 'q' was not declared in this scope
   29 |     if(x >= 0) mx(q[x].Y.X, z1[v]), mx(z1[v << 1], z1[v]);
      |                   ^
sweeping.cpp:8:19: note: in definition of macro 'mx'
    8 | #define mx(x, y) (x = max(x, y))
      |                   ^
sweeping.cpp:30:19: error: 'q' was not declared in this scope
   30 |     if(y >= 0) mx(q[y].Y.X, z1[v]), mx(z1[v << 1 | 1], z1[v]);
      |                   ^
sweeping.cpp:8:19: note: in definition of macro 'mx'
    8 | #define mx(x, y) (x = max(x, y))
      |                   ^
sweeping.cpp: In function 'void p2(ll)':
sweeping.cpp:36:19: error: 'q' was not declared in this scope
   36 |     if(x >= 0) mx(q[x].Y.Y, z2[v]), mx(z2[v << 1], z2[v]);
      |                   ^
sweeping.cpp:8:19: note: in definition of macro 'mx'
    8 | #define mx(x, y) (x = max(x, y))
      |                   ^
sweeping.cpp:37:19: error: 'q' was not declared in this scope
   37 |     if(y >= 0) mx(q[y].Y.Y, z2[v]), mx(z2[v << 1 | 1], z2[v]);
      |                   ^
sweeping.cpp:8:19: note: in definition of macro 'mx'
    8 | #define mx(x, y) (x = max(x, y))
      |                   ^
sweeping.cpp: In function 'void g1(ll, ll, ll, ll, ll)':
sweeping.cpp:46:22: error: 'q' was not declared in this scope
   46 |         if(gt < 0 || q[m1[v]].Y.X < q[gt].Y.X) gt = m1[v];
      |                      ^
sweeping.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void g2(ll, ll, ll, ll, ll)':
sweeping.cpp:59:22: error: 'q' was not declared in this scope
   59 |         if(gt < 0 || q[m2[v]].Y.Y < q[gt].Y.Y) gt = m2[v];
      |                      ^
sweeping.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void d1(ll)':
sweeping.cpp:69:38: error: 'q' was not declared in this scope
   69 |     m1[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.X < q[y].Y.X ? x : y);
      |                                      ^
sweeping.cpp: In function 'void d2(ll)':
sweeping.cpp:74:38: error: 'q' was not declared in this scope
   74 |     m2[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.Y < q[y].Y.Y ? x : y);
      |                                      ^
sweeping.cpp: In function 'void pt1(ll, ll, ll, ll, bool)':
sweeping.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void pt2(ll, ll, ll, ll, bool)':
sweeping.cpp:99:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void up1(ll, ll, ll, ll, ll, ll)':
sweeping.cpp:108:23: error: 'q' was not declared in this scope
  108 |         if(y >= 0) mx(q[y].Y.X, x), mx(z1[v], x);
      |                       ^
sweeping.cpp:8:19: note: in definition of macro 'mx'
    8 | #define mx(x, y) (x = max(x, y))
      |                   ^
sweeping.cpp:111:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void up2(ll, ll, ll, ll, ll, ll)':
sweeping.cpp:120:23: error: 'q' was not declared in this scope
  120 |         if(y >= 0) mx(q[y].Y.Y, x), mx(z2[v], x);
      |                       ^
sweeping.cpp:8:19: note: in definition of macro 'mx'
    8 | #define mx(x, y) (x = max(x, y))
      |                   ^
sweeping.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |     ll m = l + r >> 1;
      |            ~~^~~
sweeping.cpp: In function 'void doj(ll, ll, ll, ll, ll, ll)':
sweeping.cpp:139:23: error: 'q' was not declared in this scope
  139 |             ll a = in[q[i].X], b = q[i].Y.X;
      |                       ^
sweeping.cpp:140:24: error: 'q1' was not declared in this scope; did you mean 'a1'?
  140 |             if(a < -1) q1[a1] = q[i], o1[a1++] = 1;
      |                        ^~
      |                        a1
sweeping.cpp:141:28: error: 'q1' was not declared in this scope; did you mean 'a1'?
  141 |             else if(a < 0) q1[a2] = q[i], o1[a2--] = 1;
      |                            ^~
      |                            a1
sweeping.cpp:143:16: error: 'b' was not declared in this scope
  143 |             ax[b] = q[a].Y.X, ay[b] = q[a].Y.Y;
      |                ^
sweeping.cpp:147:20: error: 'q' was not declared in this scope
  147 |             ll a = q[i].X;
      |                    ^
sweeping.cpp:150:28: error: 'q1' was not declared in this scope; did you mean 'a1'?
  150 |                 if(r2 < a) q1[a2] = {a - r2, {0, 0}}, o1[a2--] = 2;
      |                            ^~
      |                            a1
sweeping.cpp:155:17: error: 'q1' was not declared in this scope; did you mean 'a1'?
  155 |                 q1[a1] = q[i], o1[a1++] = 2;
      |                 ^~
      |                 a1
sweeping.cpp:161:21: error: 'pi' was not declared in this scope; did you mean 'i'?
  161 |                     pi p = q[gt];
      |                     ^~
      |                     i
sweeping.cpp:162:31: error: 'p' was not declared in this scope
  162 |                     q1[a1] = {p.X, {x - a + n, p.Y.Y}}, o1[a1++] = 4, in[p.X] = -2;
      |                               ^
sweeping.cpp:168:20: error: 'q' was not declared in this scope
  168 |             ll a = q[i].X;
      |                    ^
sweeping.cpp:171:28: error: 'q1' was not declared in this scope; did you mean 'a1'?
  171 |                 if(c2 < a) q1[a1] = {a - c2, {0, 0}}, o1[a1++] = 3;
      |                            ^~
      |                            a1
sweeping.cpp:176:17: error: 'q1' was not declared in this scope; did you mean 'a1'?
  176 |                 q1[a2] = q[i], o1[a2--] = 3;
      |                 ^~
      |                 a1
sweeping.cpp:182:21: error: 'pi' was not declared in this scope; did you mean 'i'?
  182 |                     pi p = q[gt];
      |                     ^~
      |                     i
sweeping.cpp:183:31: error: 'p' was not declared in this scope
  183 |                     q1[a2] = {p.X, {p.Y.X, y - a + n}}, o1[a2--] = 4, in[p.X] = -1;
      |                               ^
sweeping.cpp:189:13: error: 'pi' was not declared in this scope; did you mean 'i'?
  189 |             pi p = q[i];
      |             ^~
      |             i
sweeping.cpp:190:16: error: 'p' was not declared in this scope
  190 |             if(p.Y.X > x + c2) q1[a1] = p, in[p.X] = -2, o1[a1++] = 4;
      |                ^
sweeping.cpp:190:32: error: 'q1' was not declared in this scope; did you mean 'a1'?
  190 |             if(p.Y.X > x + c2) q1[a1] = p, in[p.X] = -2, o1[a1++] = 4;
      |                                ^~
      |                                a1
sweeping.cpp:191:37: error: 'q1' was not declared in this scope; did you mean 'a1'?
  191 |             else if(p.Y.Y > y + r2) q1[a2] = p, in[p.X] = -1, o1[a2--] = 4;
      |                                     ^~
      |                                     a1
sweeping.cpp:197:9: error: 'q' was not declared in this scope
  197 |         q[i] = q1[i], o[i] = o1[i];
      |         ^
sweeping.cpp:197:16: error: 'q1' was not declared in this scope; did you mean 'a1'?
  197 |         q[i] = q1[i], o[i] = o1[i];
      |                ^~
      |                a1
sweeping.cpp: In function 'int main()':
sweeping.cpp:210:33: error: 'q' was not declared in this scope
  210 |         scanf("%d %d", &x, &y), q[i] = {i, {x, y}}, in[i] = i, o[i] = 4;
      |                                 ^
sweeping.cpp:216:35: error: 'q' was not declared in this scope
  216 |         if(o[i] < 4) scanf("%d", &q[i].X);
      |                                   ^
sweeping.cpp:217:30: error: 'q' was not declared in this scope
  217 |         else scanf("%d %d", &q[i].Y.X, &q[i].Y.Y), in[cnt] = i, q[i].X = cnt++;
      |                              ^
sweeping.cpp:218:23: error: 'q' was not declared in this scope
  218 |         if(o[i] == 1) q[i].X--, q[i].Y.X = ca++;
      |                       ^
sweeping.cpp:206:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |     scanf("%d %d %d", &n, &m, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:215:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         scanf("%d", &o[i]);
      |         ~~~~~^~~~~~~~~~~~~