oj.uz

Submission #21032

# Submission time Handle Problem Language Result Execution time Memory
21032 2017-03-30T08:08:04 Z model_code Ruka (COI15_ruka) C++11
100 / 100
 1296 ms 17856 KB 
#include <cstdio>
#include <cstring>
#include <cassert>

#include <algorithm>
#include <iostream>
#include <deque>
#include <map>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAX = 100100;

int N, Q;
int dx[MAX], dy[MAX];

struct Loga {
  map<int, int> F;

  void update(int x, int w) {
    for (x += 2e8; x < 4e8; x += x&-x) F[x] += w;
  }

  int query(int x) {
    int ret = 0;
    for (x += 2e8; x > 0; x -= x&-x) ret += F[x];
    return ret;
  }
};

struct Trans {
  int add = 0;
  Loga L;
  deque<int> D;

  void push(int x) {
    L.update(x - add, 1);
    D.push_front(x - add);
  }
  
  void pop() {
    L.update(D.front(), -1);
    D.pop_front();
  }
  
  void update(int w) { add += w; }
  int count() { return L.query(-add); }
};

Trans Lx, Hx;
Trans Ly, Hy;

void push(int &px, int &py, int i) {
  Lx.push(min(px, px + dx[i]));
  Hx.push(max(px, px + dx[i]));
    
  Ly.push(min(py, py + dy[i]));
  Hy.push(max(py, py + dy[i]));
}

void pop() {
  Lx.pop(); Hx.pop();
  Ly.pop(); Hy.pop();
}

void update(int nx, int ny, int i) {
  Lx.update(nx - dx[i]);
  Hx.update(nx - dx[i]);

  Ly.update(ny - dy[i]);
  Hy.update(ny - dy[i]);
}

int segment(int px, int py, int i) {
  int ret = 0;
  if (min(px, px + dx[i]) < 0 && max(px, px + dx[i]) > 0) ++ret;
  if (min(py, py + dy[i]) < 0 && max(py, py + dy[i]) > 0) ++ret;
  return ret;
}

int main() {
  scanf("%d", &N);

  int px = 1, py = 1;
  REP(i, N) {
    scanf("%d%d", dx+i, dy+i);
    px += dx[i];
    py += dy[i];
  }

  for (int i = N-1; i >= 0; --i) {
    px -= dx[i];
    py -= dy[i];
    if (i) push(px, py, i);
  }

  int i = 0;
  int before = segment(px, py, i);

  scanf("%d", &Q);
  while (Q--) {
    char c; scanf(" %c", &c);
    
    if (c == 'B' && i > 0) {
      push(px, py, i);
      before -= segment(px, py, i--);
      px -= dx[i];
      py -= dy[i];
    }

    if (c == 'F' && i+1 < N) {
      pop();
      px += dx[i];
      py += dy[i];
      before += segment(px, py, ++i);
    }

    if (c == 'C') {
      int nx, ny; scanf("%d%d", &nx, &ny);
      update(nx, ny, i);
      before -= segment(px, py, i);
      dx[i] = nx;
      dy[i] = ny;
      before += segment(px, py, i);
    }

    if (c == 'Q') {
      int ans = before;
      ans += Lx.count() - Hx.count();
      ans += Ly.count() - Hy.count();
      printf("%d\n", ans);
    }
  }
  
  return 0;
}

Compilation message

ruka.cpp: In function 'int main()':
ruka.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
ruka.cpp:92:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", dx+i, dy+i);
                              ^
ruka.cpp:106:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Q);
                  ^
ruka.cpp:108:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     char c; scanf(" %c", &c);
                             ^
ruka.cpp:125:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int nx, ny; scanf("%d%d", &nx, &ny);
                                          ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2940 KB Output is correct
2 Correct 3 ms 2940 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 2940 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2940 KB Output is correct
2 Correct 3 ms 2940 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 2940 KB Output is correct
5 Correct 359 ms 8220 KB Output is correct
6 Correct 319 ms 9144 KB Output is correct
7 Correct 293 ms 6372 KB Output is correct
8 Correct 306 ms 6636 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2940 KB Output is correct
2 Correct 3 ms 2940 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 2940 KB Output is correct
5 Correct 359 ms 8220 KB Output is correct
6 Correct 319 ms 9144 KB Output is correct
7 Correct 293 ms 6372 KB Output is correct
8 Correct 306 ms 6636 KB Output is correct
9 Correct 1126 ms 17064 KB Output is correct
10 Correct 1296 ms 17856 KB Output is correct
11 Correct 1008 ms 13368 KB Output is correct
12 Correct 1136 ms 14688 KB Output is correct