oj.uz

Submission #202567

# Submission time Handle Problem Language Result Execution time Memory
202567 2020-02-17T01:51:34 Z galen_colin Wall (IOI14_wall) C++14
32 / 100
 3000 ms 28656 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 = 700;

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

# Verdict Execution time Memory Grader output
1 Correct 8 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 33 ms 5496 KB Output is correct
5 Correct 25 ms 5496 KB Output is correct
6 Correct 26 ms 5368 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 260 ms 19196 KB Output is correct
3 Correct 953 ms 9624 KB Output is correct
4 Correct 2724 ms 19316 KB Output is correct
5 Correct 869 ms 17656 KB Output is correct
6 Correct 883 ms 17528 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4984 KB Output is correct
2 Correct 10 ms 5240 KB Output is correct
3 Correct 12 ms 5112 KB Output is correct
4 Correct 33 ms 5496 KB Output is correct
5 Correct 26 ms 5368 KB Output is correct
6 Correct 26 ms 5368 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 256 ms 19196 KB Output is correct
9 Correct 919 ms 9720 KB Output is correct
10 Correct 2764 ms 19320 KB Output is correct
11 Correct 862 ms 20728 KB Output is correct
12 Correct 860 ms 26072 KB Output is correct
13 Correct 8 ms 4984 KB Output is correct
14 Correct 267 ms 25092 KB Output is correct
15 Correct 167 ms 7032 KB Output is correct
16 Execution timed out 3083 ms 28656 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 10 ms 5244 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 33 ms 5496 KB Output is correct
5 Correct 26 ms 5368 KB Output is correct
6 Correct 26 ms 5368 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 264 ms 19196 KB Output is correct
9 Correct 944 ms 9828 KB Output is correct
10 Correct 2745 ms 19448 KB Output is correct
11 Correct 896 ms 17784 KB Output is correct
12 Correct 867 ms 17528 KB Output is correct
13 Correct 8 ms 4984 KB Output is correct
14 Correct 292 ms 19324 KB Output is correct
15 Correct 166 ms 6520 KB Output is correct
16 Execution timed out 3064 ms 19064 KB Time limit exceeded
17 Halted 0 ms 0 KB -