oj.uz

Submission #202571

# Submission time Handle Problem Language Result Execution time Memory
202571 2020-02-17T02:38:02 Z galen_colin Wall (IOI14_wall) C++14
100 / 100
 1466 ms 179320 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;

struct state {
    pii free;
    int en;
    
    state() {
        free = mp(0, 100000);
        en = -1;
    }
    state(pii a, int b) {
        free = a;
        en = b;
    }
};
typedef struct state state;

vector<state> tree;

state combine(state a, state b) {
    if (b.en != -1) {
        return b;
    } else if (a.en != -1) {
        if (a.en < b.free.f) return state(a.free, b.free.f);
        else if (a.en > b.free.s) return state(a.free, b.free.s);
        else return state(a.free, a.en);
    } else {
        pii isect = mp(max(a.free.f, b.free.f), min(a.free.s, b.free.s));
        // cout << a.free << " " << b.free << " " << isect << endl;
        if (isect.f > isect.s) {
            if (a.free.f < b.free.f) return state(b.free, b.free.f);
            else return state(b.free, b.free.s);
        } else return state(isect, -1);
    }
}

state update(state s, int tl, int tr, int loc, int ind) {
    if (loc < tl || loc > tr) return tree[ind];
    
    if (tl == tr) return tree[ind] = s;
    
    int mid = (tl + tr) / 2;
    state a = update(s, tl, mid, loc, 2 * ind + 1);
    state b = update(s, mid + 1, tr, loc, 2 * ind + 2);
    return tree[ind] = combine(a, b);
}

// 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[2000005], en[2000005];
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;
  tree = vector<state>(4 * q);
  
  int mn = 0, mx = 0;
  f0r(i, q) {
    mn = min(mn, height[i]);
    mx = max(mx, height[i]);
  }
 
  f0r(i, q) {
      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)));
  }
  
  f0r(i, n) {
      for (pair<int, pii> x: st[i]) {
          pii v = x.s;
          state y = state();
          if (v.f == 1) {
              y.free.f = v.s;
          } else y.free.s = v.s;
          update(y, 0, q - 1, x.f, 0);
      }
      for (pair<int, pii> x: en[i]) {
          pii v = x.s;
          state y = state();
          update(y, 0, q - 1, x.f, 0);
      }
      
      state s = tree[0];
    //   cout << s.free << " " << s.en << endl;
      if (s.en != -1) a[i] = s.en;
      else if (a[i] < s.free.f) a[i] = s.free.f;
      else if (a[i] > s.free.s) a[i] = s.free.s;
  }
 
//   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 buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:186:15: warning: variable 'v' set but not used [-Wunused-but-set-variable]
           pii v = x.s;
               ^
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 71 ms 94328 KB Output is correct
2 Correct 67 ms 94672 KB Output is correct
3 Correct 66 ms 94456 KB Output is correct
4 Correct 73 ms 95008 KB Output is correct
5 Correct 68 ms 94972 KB Output is correct
6 Correct 71 ms 94968 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94328 KB Output is correct
2 Correct 603 ms 137608 KB Output is correct
3 Correct 546 ms 115960 KB Output is correct
4 Correct 1466 ms 146424 KB Output is correct
5 Correct 1000 ms 144612 KB Output is correct
6 Correct 986 ms 143960 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94328 KB Output is correct
2 Correct 66 ms 94840 KB Output is correct
3 Correct 72 ms 94456 KB Output is correct
4 Correct 73 ms 94968 KB Output is correct
5 Correct 73 ms 94984 KB Output is correct
6 Correct 73 ms 94968 KB Output is correct
7 Correct 60 ms 94200 KB Output is correct
8 Correct 601 ms 137736 KB Output is correct
9 Correct 531 ms 115960 KB Output is correct
10 Correct 1424 ms 146372 KB Output is correct
11 Correct 1002 ms 145184 KB Output is correct
12 Correct 972 ms 143980 KB Output is correct
13 Correct 62 ms 94200 KB Output is correct
14 Correct 597 ms 137868 KB Output is correct
15 Correct 122 ms 97776 KB Output is correct
16 Correct 1457 ms 146668 KB Output is correct
17 Correct 985 ms 143700 KB Output is correct
18 Correct 980 ms 143096 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94328 KB Output is correct
2 Correct 66 ms 94840 KB Output is correct
3 Correct 65 ms 94456 KB Output is correct
4 Correct 72 ms 95100 KB Output is correct
5 Correct 68 ms 94968 KB Output is correct
6 Correct 69 ms 94968 KB Output is correct
7 Correct 61 ms 94304 KB Output is correct
8 Correct 603 ms 137868 KB Output is correct
9 Correct 558 ms 116088 KB Output is correct
10 Correct 1414 ms 146360 KB Output is correct
11 Correct 995 ms 144724 KB Output is correct
12 Correct 966 ms 143864 KB Output is correct
13 Correct 63 ms 94328 KB Output is correct
14 Correct 604 ms 137804 KB Output is correct
15 Correct 127 ms 97784 KB Output is correct
16 Correct 1442 ms 146552 KB Output is correct
17 Correct 983 ms 143848 KB Output is correct
18 Correct 981 ms 142972 KB Output is correct
19 Correct 1221 ms 168984 KB Output is correct
20 Correct 1223 ms 176680 KB Output is correct
21 Correct 1246 ms 179300 KB Output is correct
22 Correct 1228 ms 176908 KB Output is correct
23 Correct 1216 ms 176956 KB Output is correct
24 Correct 1208 ms 176884 KB Output is correct
25 Correct 1227 ms 176688 KB Output is correct
26 Correct 1228 ms 179320 KB Output is correct
27 Correct 1220 ms 179232 KB Output is correct
28 Correct 1224 ms 176884 KB Output is correct
29 Correct 1211 ms 176948 KB Output is correct
30 Correct 1223 ms 176780 KB Output is correct