제출 #1123114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123114		LinhLewLew	Ruka (COI15_ruka)	C++20	0 / 100	1 ms	832 KiB

ruka

// PhuThuyRuntime <3
// A secret makes a woman woman

#include <bits/stdc++.h>

using namespace std;

#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) ((1 << j) ^ i)
#define onbit(i, j) ((1 << j) | i)
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int n, dx[N], dy[N], m;
void inp(){
     cin >> n;
     fo(i, 1, n) cin >> dx[i] >> dy[i];
     cin >> m;
}
struct Fenwick{
     int bit[200 * N];

     void update(int x, int w) {
          for (x += 1e7; x < 2e7; x += x&-x) bit[x] += w;
     }

     int query(int x) {
          int ret = 0;
          for (x += 1e7; x > 0; x -= x&-x) ret += bit[x];
          return ret;
     }
};

struct Trans {
     int add = 0;
     Fenwick 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;
}
void sol(){
     int px = 1, py = 1;
     fo(i, 1, n) px += dx[i], py += dy[i];
     foi(i, n, 1){
          px -= dx[i], py -= dy[i];
          if(i > 1) push(px, py, i);
     }
     int i = 0;
     int ans = segment(px, py, i);
     while(m--){
          char ch; cin >> ch;
          if(ch == 'B' && i > 1){
               push(px, py, i);
               ans -= segment(px, py, i--);
               px -= dx[i], py -= dy[i];
          }
          if(ch == 'F' && i < n){
               pop();
               px += dx[i];
               py += dy[i];
               ans += segment(px, py, ++i);
          }
          if(ch == 'C'){
               int nx, ny; cin >> nx >> ny;
               update(nx, ny, i);
               ans -= segment(px, py, i);
               dx[i] = nx, dy[i] = ny;
               ans += segment(px, py, i);
          }
          if(ch == 'Q'){
               cout << ans + Lx.count() - Hx.count() + Ly.count() - Hy.count(), el
          }
     }
}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     inp();
     sol();
     return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 35
• Subtask 3: 0 / 56