oj.uz

Submission #333420

# Submission time Handle Problem Language Result Execution time Memory
333420 2020-12-05T22:16:29 Z gmyu Secret (JOI14_secret) C++14
0 / 100
 508 ms 9964 KB 
/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

#include "secret.h"

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

/**
* RMQ use sparse table, O(N log N) memory and setip, O(1) query
* https://usaco.guide/plat/DC-SRQ
*/
int rqN;
vi x;
map<pair<int, int>, int> ans;

int rq[18][MAXV], rqmask[MAXV];      /// 18 = ceil(log2(n))


int getAns(int v1, int v2) {
    if(v1>v2) swap(v1, v2);
    pii vp = mp(v1, v2);
    if(ans.find(vp) == ans.end()) ans[vp] = Secret(v1, v2);
    return ans[vp];
}

void divi(int l, int r, int lev = 0) { // generate dat and mask
    if (l == r) return;
    int m = (l+r)/2;
    rq[lev][m] = x[m]; for(int i = m-1; i >= l; i--) rq[lev][i] = getAns(x[i], rq[lev][i+1]);
    rq[lev][m+1] = x[m+1]; for(int i = m+2; i <= r; i++) rq[lev][i] = getAns(rq[lev][i-1], x[i]);
    for(int i = m+1; i <= r; i++) rqmask[i] ^= 1<<lev;
    divi(l,m,lev+1); divi(m+1,r,lev+1);
}
int que(int l, int r) {         /// [ , ]
    if(l == r) return x[l];
    int bits = __builtin_ctz(rqmask[l]^rqmask[r]);
    return getAns(rq[bits][l], rq[bits][r]);
}

void Init(int N, int A[]) {
    rqN = N;
    for(int i = 0; i < N; i++) x.pb(A[i]);
    divi(0, N-1);
}
int Query(int L, int R) {
    que(L, R);
}

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:99:1: warning: no return statement in function returning non-void [-Wreturn-type]
   99 | }
      | ^
secret.cpp: In function 'void setIO(std::string)':
secret.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
secret.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 143 ms 5484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 139 ms 5356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 504 ms 9964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 504 ms 9964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 505 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 508 ms 9780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 508 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 507 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 508 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)