Submission #303383

# Submission time Handle Problem Language Result Execution time Memory
303383 2020-09-20T09:23:48 Z vaaven Furniture (JOI20_furniture) C++14
0 / 100
5000 ms 816 KB
/*                                                                                                    
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .o:--...```..---+/`                                        
                                       `/y+o/---....---:+o.                                         
                                   `...````-os+/:---:/+o/--.`                                       
              `-/+++++/:.      `...`       :h+d+oooo+/+-`   ...                                     
            `/++//:::://++-`....`         -.`//````````:`     `..`                                  
           `o+/::------://o/`           `-` -.          -`       `..`                               
  `....o+:-++/:--.```..-://s.        `-`  .-              -`          `-o: .-//::::/:-`             
          `:s+/:--....-::/+s-`      .-   `-                -`           -///:--------:/:`           
            .:ooo+++++osso-`    `.:-...`/` ./::-------:/:`   -`         :+--..``````.--:+:...-+:-`  
             `.-/+++++/+-.-`    -.   ``:so:/:--.......--:+`  `-```````o+/+--..`````..--:o/-..:s+:.  
                 ```````:``.. `-`     -` `+:--..`````..--/+-.../.`````..-o:--.......---/o.    `     
                        `:  `:-      -.  .o:--..`` ``..--:o`   `-`      `:o+:--------:+o-`          
                         `-`-...    ..   .o/--...```..--:+/`    `-`     `oy/so/////++o/.`           
                          -/`  `-` `- ``+s/o/:---...---:++.      `-`   .-../d://///:-.`             
                `.---..``-..-    .-/..`````-oo+/:::::/+o+-        `-``-`  `-.  ````                 
             `:++++/+++++-  ..``.-/:`      /y-:/++o++/:.`..`       ./.   `-                         
            -++/::::::://+/..:-``:` ..   `-.`  ```.```    `..`   `..`-` `-                          
       ``  -o//:--....-::/++` -.-`   `-`.-`                 `..`..`  `-.-                           
  -----ss+:++/:--.```..-://s.  /.     `::                    `-:.     ./`                           
  `````/:..+o/::-..``.--:/+s. ..-`   `-``-`                 ..` `-`  `-`-`                          
          `-s+/::-----::/+oo---``-` ..    .:-    ```      .-`     .-.-  `-`                         
           `:oo+//::://+os/..:`..-/:`      :y.-:::::::.`.-`        ./-`  `-`                        
            `./+oooooooo+/.`-    .-:...`.. .//:-------://`        `- `..` `:.                       
              ``.-::::-.``-/`  `-` `-  `oo:+:--.......--:/`      `-    `.:--h.``..```               
                          -.-`.-    .-   `+:--..`````..--//`    `-       /s-//::::::::.             
                         -` `/-      ..  .o:--..`` ``..--:o.```.-        `//:--------://`           
                        -` .-`.-`     -.`-o/--...```..--:+/.``-:....``:-.+:--....`...--:+`          
                       ..`-.   `-.   ``:os:o/:---...---:++.  `-     ``///+:-..``````.--:+-````-.`   
              `.:///////.-`      .:-..` -``-+o+/:::::/+o/.  `-         `:+:-..`````..--:o/:--/ys+-  
            `-++///////+o/. ``....`-.    :` `.:++++++/:.`  .-           -o/---......---/o.   `.`    
           `++//:-----::/+o:..`     .-`   :    ```````    .-           `+so+:--------:++-`          
  `````:-``:o/::-..`..--:/+o`         -.  `-             .-          `../../+o+////+o+:.`           
  -----syo/o+/:--.```..-://s.          .-` `-           .-        `...     ``-:////:-``             
       .` `/s//:--....-::/+s.            -. `-`        .-       `..`                                
           .+o+/:::--:://+s/-..`          .::+y  ```  .-     `..`                                   
            ./oo++////+oso-`   `....       :y-+:::::::/`   ...                                      
             `.:+oooooo/-`         `....-. .//:-------:/:-.`                                        
                ``...``                 /+:+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .+/--...```..--:+/`                                        
                                         `-o/:---...---:++.                                         
                                          `-+o+/:---:/+o/.                                          
                                            `.:+oooo+/-.`                                           
                                               ``````                                               
*/
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("section-anchors")
// #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
// #pragma GCC optimize("vpt")
// #pragma GCC optimize("rename-registers")
// #pragma GCC optimize("move-loop-invariants")
// #pragma GCC optimize("unswitch-loops")
// #pragma GCC optimize("function-sections")
// #pragma GCC optimize("data-sections")
// #pragma GCC optimize("branch-target-load-optimize")
// #pragma GCC optimize("branch-target-load-optimize2")
// #pragma GCC optimize("btr-bb-exclusive")
// #pragma comment(linker, "/STACK:367077216")
#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define DEBUG
#define fi first
#define se second
#define pqueue priority_queue
#define pb(x) push_back(x)
//#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long  long
#define mk(a, b) make_pair(a, b)
 
using namespace std;
      
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector< vector<ll> > vvll;
typedef vector<char> vc;
      
const int inf = 1e9 + 228;
const ll infll = 1e18;
const ll MOD = 1e9 + 7;
//static const int maxn = 1e6 + 228;
const ld eps = 1e-5;
const int K = 31;
const ld eps2 = 1e-9;
const ll MOD2 = 998244353;
const ll dosz = 5e5;
const ll SZ = (1<<18);
const ld PI = 3.1415926535;
     
void fast_io(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // freopen("a.in", "r", stdin);
  // freopen("digit.out", "w", stdout);
}

const int maxn = 1001;
int kek[maxn][maxn];
int n, m;
set<pii> first, second; 
set<int> lol[maxn];

void dfs1(int i, int j){
  if(kek[i][j] == 1)
    return;
  if(i>=n || i<0 || j>=m || j<0)
    return;
  first.insert(make_pair(i, j)); 
  dfs1(i+1, j);
  dfs1(i, j+1);
}

void dfs2(int i, int j){
  if(kek[i][j] == 1)
    return;
  if(i>=n || i<0 || j>=m || j<0)
    return;
  second.insert(make_pair(i, j)); 
  dfs2(i-1, j);
  dfs2(i, j-1);
}


void solve(){ 
  cin >> n >> m;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> kek[i][j];
    }
  }
  dfs1(0, 0);
  dfs2(n-1, m-1);
  for(pii i:first){
    if(second.count(i)){
      lol[i.second].insert(i.first);
    }
  }
  int q;
  cin >> q;
  for(int i=0; i<q; i++){
    int a, b;
    cin >> a >> b;
    a--, b--;
    if(lol[b].count(a) && lol[b].size()==1){
      cout << 0 << endl;
    } else{
      set<int> lst;
      lst = lol[b];
      lst.erase(a);
      auto it = lst.lower_bound(a);
      bool skip = false;
      vi to_erase;
      if(!b){
        while(*(--lst.end()) > a){
          lst.erase((--lst.end()));
        }
      } else if(it!=lst.end()){
        bool ok = false;
        for(auto it2 = it; it2!=lst.end(); it2++){
          if(lol[b-1].count(*it2)){
            break;
          }
          to_erase.pb(*it2);
        }
      }
      it = lst.lower_bound(a);
      if(b==m-1){
        while(*(--lst.begin()) < a){
          lst.erase(--lst.end());
        }
      } else if(it != lst.begin()){
        // cout << b << endl;
        for(auto it2 = --it; it2!=lst.begin(); it2--){
          if(lol[b+1].count(*it2)){
            break;
          }
          to_erase.pb(*it2);
        }
        if(!lol[b+1].count(*lst.begin())){
            to_erase.pb(*lst.begin());
            // cout << *lst.begin() << endl;
        }
      }
      for(int i:to_erase){
        // cout << i << " ";
        lst.erase(i);
      }
      if(lst.empty()){
        cout << 0 << endl;
        continue;
      }
      lol[b] = lst;
      // cout << *lst.begin() << endl;
      cout << 1 << endl;
      lol[b].erase(a);
      int cur = *lol[b].begin();  
      for(int i=b-1; i>=0; i--){
        while(*lol[i].begin() < cur){
          lol[i].erase(lol[i].begin());
        }
        cur = *lol[i].begin();
      }
      cur = *(--lol[b].end());
      for(int i=b+1; i<m; i++){
        while(*(--lol[i].end()) > cur){
          lol[i].erase(--lol[i].end());
        } 
        cur = *(--lol[i].end());
      }
    }
  }
}

signed main(){
    fast_io();
    srand(time(NULL));
    // cout << fixed << setprecision(3);
    int q = 1;
    // cin >> q;
    while(q--)
        solve();
}

Compilation message

furniture.cpp: In function 'void solve()':
furniture.cpp:191:14: warning: unused variable 'ok' [-Wunused-variable]
  191 |         bool ok = false;
      |              ^~
furniture.cpp:184:12: warning: unused variable 'skip' [-Wunused-variable]
  184 |       bool skip = false;
      |            ^~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 5038 ms 816 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 5038 ms 816 KB Time limit exceeded
2 Halted 0 ms 0 KB -