oj.uz

Submission #333422

# Submission time Handle Problem Language Result Execution time Memory
333422 2020-12-05T22:20:30 Z gmyu Secret (JOI14_secret) C++14
0 / 100
 511 ms 9708 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 1007
#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[10][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 5228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 138 ms 5228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 137 ms 5264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 501 ms 9580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 506 ms 9600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 510 ms 9656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 504 ms 9580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 503 ms 9708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 511 ms 9580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 505 ms 9708 KB Execution killed with signal 11 (could be triggered by violating memory limits)