Submission #2601082


Source Code Expand

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; scanf("%lld", &x); return x;}
ld fin(){double x; scanf("%lf", &x); return x;}
char yuyushiki[1000010]; string stin(){scanf( "%s", yuyushiki ); return yuyushiki;}

// head

ll ans;
multiset<ll> ss;

ll h, w, n, m, d;
ll a[60];
vector<ll> f[100010];

ll prv(ll x){
  auto ite = ss.upper_bound(x);
  if(ite == ss.begin()){
    return -INFLL;
  }
  ite--;
  return *ite;
}

ll nex(ll x){
  auto ite = ss.upper_bound(x);
  if(ite == ss.end()){
    return INFLL;
  }
  return *ite;
}

void add(ll x){
  // cout << "A " << x << endl;
  if(ss.find(x) != ss.end()){
    ss.insert(x);
    return;
  }
  ll pr = prv(x);
  ll ne = nex(x);
  ss.insert(x);
  if(ne - pr - 1 <= d){
    return;
  }
  ans++;
  if(ne - x - 1 <= d){
    ans += ne - x - 1;
  }
  if(x - pr - 1 <= d){
    ans += x - pr - 1;
  }
}

void del(ll x){
  // cout << "D " << x << endl;
  ss.erase(ss.find(x));
  if(ss.find(x) != ss.end()){
    return;
  }
  ll pr = prv(x);
  ll ne = nex(x);
  if(ne - pr - 1 <= d){
    return;
  }
  ans--;
  if(ne - x - 1 <= d){
    ans -= ne - x - 1;
  }
  if(x - pr - 1 <= d){
    ans -= x - pr - 1;
  }
}

int main(){

  h = in();
  w = in();
  n = in();
  m = in();
  d = in();
  REP(i, n){
    a[i] = in() - 1;
  }
  REP(i, m){
    ll b = in() - 1;
    ll c = in() - 1;
    f[c].pb(b);
    add(b*w + c);
  }

  REP(j, w){
    REP(i, n){
      add(j + a[i]);
    }
    printf("%lld\n", ans);
    REP(i, n){
      del(j + a[i]);
    }
    YYS(b, f[j]){
      del(b*w + j);
      add((b+1)*w + j);
    }
  }
  
  return 0;
}

Submission Info

Submission Time
Task E - 祝日
User joisino
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2726 Byte
Status AC
Exec Time 3674 ms
Memory 12800 KB

Compile Error

./Main.cpp: In function ‘ll in()’:
./Main.cpp:35:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll in(){long long int x; scanf("%lld", &x); return x;}
                                           ^
./Main.cpp: In function ‘ld fin()’:
./Main.cpp:36:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ld fin(){double x; scanf("%lf", &x); return x;}
                                    ^
./Main.cpp: In function ‘std::string stin()’:
./Main.cpp:37:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 char yuyushiki[1000010]; string stin(){scanf( "%s", yuyushiki ); return yuyushiki;}
                                                                ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 600 / 600 100 / 100
Status
AC × 4
AC × 22
AC × 56
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, sample-01.txt, sample-02.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 228 ms 10880 KB
01-02.txt AC 219 ms 9984 KB
01-03.txt AC 122 ms 8192 KB
01-04.txt AC 39 ms 4480 KB
01-05.txt AC 196 ms 8832 KB
01-06.txt AC 189 ms 8320 KB
01-07.txt AC 185 ms 8048 KB
01-08.txt AC 29 ms 4608 KB
01-09.txt AC 223 ms 9600 KB
01-10.txt AC 31 ms 4224 KB
01-11.txt AC 158 ms 9856 KB
01-12.txt AC 166 ms 9600 KB
01-13.txt AC 177 ms 9856 KB
01-14.txt AC 66 ms 6016 KB
01-15.txt AC 205 ms 11136 KB
01-16.txt AC 5 ms 2688 KB
01-17.txt AC 42 ms 4352 KB
01-18.txt AC 209 ms 8320 KB
01-19.txt AC 228 ms 10880 KB
01-20.txt AC 228 ms 10112 KB
02-01.txt AC 2260 ms 10880 KB
02-02.txt AC 710 ms 9216 KB
02-03.txt AC 720 ms 10112 KB
02-04.txt AC 1265 ms 12160 KB
02-05.txt AC 2229 ms 10752 KB
02-06.txt AC 1131 ms 9344 KB
02-07.txt AC 185 ms 8048 KB
02-08.txt AC 268 ms 3456 KB
02-09.txt AC 1439 ms 9984 KB
02-10.txt AC 109 ms 3840 KB
02-11.txt AC 1578 ms 11776 KB
02-12.txt AC 498 ms 9472 KB
02-13.txt AC 684 ms 9088 KB
02-14.txt AC 120 ms 3712 KB
02-15.txt AC 581 ms 9088 KB
02-16.txt AC 23 ms 2688 KB
02-17.txt AC 69 ms 4352 KB
02-18.txt AC 260 ms 8320 KB
02-19.txt AC 2333 ms 12800 KB
02-20.txt AC 187 ms 8052 KB
02-21.txt AC 350 ms 3328 KB
02-22.txt AC 3 ms 2560 KB
02-23.txt AC 3674 ms 11136 KB
02-24.txt AC 1877 ms 9216 KB
02-25.txt AC 1274 ms 11136 KB
02-26.txt AC 4 ms 2560 KB
02-27.txt AC 88 ms 2688 KB
02-28.txt AC 362 ms 2944 KB
02-29.txt AC 185 ms 8064 KB
02-30.txt AC 187 ms 8192 KB
02-31.txt AC 187 ms 8192 KB
02-32.txt AC 203 ms 2816 KB
sample-01.txt AC 2 ms 2560 KB
sample-02.txt AC 2 ms 2560 KB
sample-03.txt AC 2 ms 2560 KB
sample-04.txt AC 2 ms 2560 KB