Submission #973556

#	Time	Username	Problem	Language	Result	Execution time	Memory
973556		vjudge1	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1318 ms	154132 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+20;

struct BIT2d{
   int n;
   vector<pair<int, int>> t[N];
   void init(int _n){
      n=_n;
      for (int i=1; i<=n; ++i) t[i].emplace_back(-1, 0);
   }
   void fake_update(int x, int y){
      for (int i=x; i<=n; i+=i&(-i)) t[i].emplace_back(y, 0);
   }
   void compress(){
      for (int i=1; i<=n; ++i){
         sort(t[i].begin(), t[i].end());
         t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
      }
   }
   void update(int x, int y, int val){
      for (int i=x; i<=n; i+=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, (int)1e9))-t[i].begin()-1; j<(int)t[i].size(); j+=j&(-j)){
            t[i][j].second+=val;
         }
      }
   }
   int get(int x, int y){
      int ans=0;
      for (int i=x; i; i-=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, (int)1e9))-t[i].begin()-1; j; j-=j&(-j)){
            ans+=t[i][j].second;
         }
      }
      return ans;
   }
   int get(int x, int y, int z, int t){
      if (x>z || y>t) return 0;
      return get(z, t)-get(z, y-1)-get(x-1, t)+get(x-1, y-1);
   }
} bit1, bit2, bit3, bit4;

const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
int r, c;

void init(int R, int C, int sr, int sc, int M, char *S) {
   r=R, c=C;
   bit1.init(r);
   bit2.init(r+1);
   bit3.init(r+1);
   bit4.init(r);
   set<pair<int, int>> st1, st2, st3, st4;
   auto insert2=[&](int x, int y){
      st2.emplace(x, y);
      st2.emplace(x, y+1);
      st2.emplace(x+1, y);
      st2.emplace(x+1, y+1);
   };
   auto insert3=[&](int x, int y){
      st3.emplace(x, y);
      st3.emplace(x+1, y);
   };
   auto insert4=[&](int x, int y){
      st4.emplace(x, y);
      st4.emplace(x, y+1);
   };
   auto insert=[&](int x, int y){
      st1.emplace(x, y);
      insert2(x, y);
      insert3(x, y);
      insert4(x, y);
   };
   insert(sr, sc);
   for (int i=0; i<M; ++i){
      if (S[i]=='N') --sr;
      if (S[i]=='S') ++sr;
      if (S[i]=='E') ++sc;
      if (S[i]=='W') --sc;
      insert(sr, sc);
   }
   for (auto &i:st1) bit1.fake_update(i.first, i.second);
   for (auto &i:st2) bit2.fake_update(i.first, i.second);
   for (auto &i:st3) bit3.fake_update(i.first, i.second);
   for (auto &i:st4) bit4.fake_update(i.first, i.second);
   bit1.compress();
   bit2.compress();
   bit3.compress();
   bit4.compress();
   for (auto &i:st1) bit1.update(i.first, i.second, 1);
   for (auto &i:st2) bit2.update(i.first, i.second, 1);
   for (auto &i:st3) bit3.update(i.first, i.second, 1);
   for (auto &i:st4) bit4.update(i.first, i.second, 1);
}

int colour(int ar, int ac, int br, int bc) {
   int V=(br-ar+1)*2+(bc-ac+1)*2+bit2.get(ar+1, ac+1, br, bc);
   int E=(br-ar+1)*2+(bc-ac+1)*2+bit3.get(ar+1, ac, br, bc)+bit4.get(ar, ac+1, br, bc);
   int CC=1;
   int cnt_out;
   if (ar==br || ac==bc) cnt_out=bit1.get(ar, ac, br, bc);
   else cnt_out=bit1.get(ar, ac, ar, bc-1)+bit1.get(ar, bc, br-1, bc)+bit1.get(br, ac+1, br, bc)+bit1.get(ar+1, ac, br, ac);
   int cnt_in=bit1.get(ar+1, ac+1, br-1, bc-1);
   if (cnt_in && !cnt_out) ++CC;
   int F=cnt_in+cnt_out;
   // cerr << V << ' ' << E << ' ' << CC << ' ' << F << '\n';
   return E-V+CC-F;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26