oj.uz

답안 #202570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202570 2020-02-17T02:03:41 Z galen_colin 벽 (IOI14_wall) C++14
61 / 100
 2792 ms 52088 KB 
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < (n); i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
 
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
 
// namespace interactor {
  
// }
 
// using namespace interactor;
 
// void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]);
 
// int main() {
//   usaco("file");
 
//   int n, q;
//   cin >> n >> q;
//   int op[q];
//   int left[q];
//   int right[q];
//   int height[q];
//   int finalHeight[n];
//   f0r(i, q) cin >> op[i] >> left[i] >> right[i] >> height[i];
//   f0r(i, n) finalHeight[i] = 0;
//   buildWall(n, q, op, left, right, height, finalHeight);
//   // buildWall(3, 3, 
//   // new int[3]{1, 1, 2},
//   // new int[3]{0, 1, 0},
//   // new int[3]{1, 2, 1},
//   // new int[3]{2, 4, 3},
//   // new int[3]{0, 0, 0});
// }
 
#include "wall.h"
 
ll n, m, k, q, Q, T, l, r, x, y, z;
ll a[1000005];
ll b[1000005];
ll c[1000005];
string s, t;
ll ans = 0;
 
vector<pair<int, pii> > st[100005], en[100005];
set<pair<int, pii> > ms;
const int block = 500;
 
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int a[]) {
  f0r(i, n) a[i] = 0;
 
  int mn = 0, mx = 0;
  f0r(i, q) {
    mn = min(mn, height[i]);
    mx = max(mx, height[i]);
  }
 
  int stop = 0;
  int last = 0;
  while (1) {
    stop += block;
    if (stop > q) stop = q;
 
    f1r(i, last, stop) {
      int l = left[i], r = right[i], h = height[i];
 
      st[l].pb(mp(i, mp(op[i], h)));
      en[r + 1].pb(mp(i, mp(op[i], h)));
    }
 
    pii free = mp(mn, mx);
    int fin = -1;
 
    f0r(i, n) {
      bool changed = 0;
      for (pair<int, pii> x: st[i]) {
        changed = 1;
        ms.insert(x);
      }
      for (pair<int, pii> x: en[i]) {
        changed = 1;
        ms.erase(x);
      }
 
      if (changed) {
        free = mp(mn, mx);
        fin = -1;
        for (pair<int, pii> x: ms) {
          pii v = x.s;
          int h = v.s;
          if (v.f == 1) {
            if (h >= free.s) {
              free.f = free.s = h;
              fin = h;
            } else if (h >= free.f) {
              free.f = h;
            }
          } else {
            if (h <= free.f) {
              free.f = free.s = h;
              fin = h;
            } else if (h <= free.s) {
              free.s = h;
            }
          }
        }
      }
 
      if (fin == -1) {
        if (a[i] < free.f) a[i] = free.f;
        else if (a[i] > free.s) a[i] = free.s;
      } else a[i] = fin;
    }
 
    f0r(i, n) {
      st[i].clear();
      en[i].clear();
    }
    ms.clear();
    last += block;
    if (stop == q) break;
  }
 
  // ao(a, n);
}
 
// int main() {
//   io;
//   // freopen("case", "r", stdin);
//   // freopen("test.txt", "r", stdin);
//   // freopen("case", "w", stdout);
//   // freopen("file.in", "r", stdin);
 
//   // usaco("file");
 
  
// }

Compilation message

wall.cpp: In function 'void usaco(std::__cxx11::string)':
wall.cpp:65:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:66:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4984 KB Output is correct
2 Correct 10 ms 5240 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 28 ms 5372 KB Output is correct
5 Correct 22 ms 5368 KB Output is correct
6 Correct 23 ms 5496 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 259 ms 19328 KB Output is correct
3 Correct 715 ms 9616 KB Output is correct
4 Correct 2432 ms 19100 KB Output is correct
5 Correct 992 ms 17272 KB Output is correct
6 Correct 983 ms 17088 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 10 ms 5240 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 28 ms 5500 KB Output is correct
5 Correct 23 ms 5368 KB Output is correct
6 Correct 24 ms 5368 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 269 ms 19184 KB Output is correct
9 Correct 724 ms 9464 KB Output is correct
10 Correct 2366 ms 19320 KB Output is correct
11 Correct 1000 ms 17616 KB Output is correct
12 Correct 992 ms 17528 KB Output is correct
13 Correct 8 ms 4984 KB Output is correct
14 Correct 260 ms 19440 KB Output is correct
15 Correct 134 ms 6520 KB Output is correct
16 Correct 2792 ms 19576 KB Output is correct
17 Correct 1046 ms 26104 KB Output is correct
18 Correct 1057 ms 26176 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 10 ms 5240 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 31 ms 5368 KB Output is correct
5 Correct 23 ms 5368 KB Output is correct
6 Correct 23 ms 5368 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 255 ms 19340 KB Output is correct
9 Correct 719 ms 9596 KB Output is correct
10 Correct 2333 ms 19576 KB Output is correct
11 Correct 1004 ms 17528 KB Output is correct
12 Correct 980 ms 17144 KB Output is correct
13 Correct 7 ms 4984 KB Output is correct
14 Correct 260 ms 19180 KB Output is correct
15 Correct 136 ms 6520 KB Output is correct
16 Correct 2791 ms 19564 KB Output is correct
17 Correct 1025 ms 26232 KB Output is correct
18 Correct 1014 ms 26140 KB Output is correct
19 Runtime error 255 ms 52088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -