oj.uz

Submission #202541

# Submission time Handle Problem Language Result Execution time Memory
202541 2020-02-16T23:42:26 Z galen_colin Wall (IOI14_wall) C++14
32 / 100
 1016 ms 46040 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() {
//   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;

vi st[100005], en[100005];
multiset<int> ms;

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int a[]) {
  f0r(i, n) a[i] = 0;
  if (n <= 10000 && q <= 5000) {
    f0r(i, q) {
      f1r(j, left[i], right[i] + 1) {
        if (op[i] == 1) {
          if (a[j] < height[i]) a[j] = height[i];
        } else {
          if (a[j] > height[i]) a[j] = height[i];
        }
      }
    }
  } else {
    bool add = 1;
    f0r(i, q) {
      if (add && op[i] == 2) {
        add = 0;

        f0r(i, n) {
          for (int x: st[i]) ms.insert(x);
          for (int x: en[i]) ms.erase(ms.find(x));
          if (ms.size()) {
            int h = *ms.rbegin();
            if (a[i] < h) a[i] = h;
          }
        }

        f0r(i, n) {
          st[i].clear();
          en[i].clear();
        }
        ms.clear();
      }

      st[left[i]].pb(height[i]);
      en[right[i] + 1].pb(height[i]);
    }

    f0r(i, n) {
      for (int x: st[i]) ms.insert(x);
      for (int x: en[i]) ms.erase(ms.find(x));
      if (ms.size()) {
        int h = *ms.begin();
        if (a[i] > h) a[i] = h;
      }
    }
  }

  // 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 7 ms 4984 KB Output is correct
2 Correct 9 ms 5112 KB Output is correct
3 Correct 9 ms 4984 KB Output is correct
4 Correct 43 ms 5240 KB Output is correct
5 Correct 32 ms 5240 KB Output is correct
6 Correct 32 ms 5240 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 633 ms 34296 KB Output is correct
3 Correct 305 ms 19508 KB Output is correct
4 Correct 1016 ms 35748 KB Output is correct
5 Correct 323 ms 32632 KB Output is correct
6 Correct 295 ms 28536 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 9 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 33 ms 5240 KB Output is correct
5 Correct 35 ms 5240 KB Output is correct
6 Correct 32 ms 5116 KB Output is correct
7 Correct 7 ms 4988 KB Output is correct
8 Correct 635 ms 34368 KB Output is correct
9 Correct 302 ms 19448 KB Output is correct
10 Execution timed out 68 ms 9696 KB Time limit exceeded (wall clock)
11 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 11 ms 5112 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Correct 33 ms 5240 KB Output is correct
5 Correct 31 ms 5240 KB Output is correct
6 Correct 31 ms 5244 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 628 ms 34500 KB Output is correct
9 Correct 300 ms 19448 KB Output is correct
10 Correct 1010 ms 37112 KB Output is correct
11 Correct 317 ms 32632 KB Output is correct
12 Correct 292 ms 28664 KB Output is correct
13 Correct 8 ms 4984 KB Output is correct
14 Incorrect 621 ms 46040 KB Output isn't correct
15 Halted 0 ms 0 KB -