oj.uz

Submission #863949

# Submission time Handle Problem Language Result Execution time Memory
863949 2023-10-21T14:20:38 Z nnhzzz Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
8 / 100
 3000 ms 10172 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024

#include<bits/stdc++.h>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define               gcd  __gcd
#define                fi  first
#define                se  second
#define                ll  long long
#define               ull  unsigned long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define        REP(i,a,b)  for(int i = (a); i<=(b); ++i)
#define       REPD(i,a,b)  for(int i = (a); i>=(b); --i)
#define   REPDIS(i,a,b,c)  for(int i = (a); i<=(b); i+=c)
#define              endl  "\n"
// #define               int  ll

//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 1e6+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int a[MAXN];
int n,q;

void sub1(){
    while(q--){
        int ok = 1,l,r,k; cin >> l >> r >> k;
        vi b;
        REP(i,l,r) b.push_back(a[i]);
        REPD(i,r-l,0){
            int ma = 0,pos = 0;
            REP(j,0,i){
                if(maxi(ma,b[j]) || ma==b[j]) pos = j;
            }
            while(pos!=i){
                if(b[pos]+b[pos+1]<=k){
                    swap(b[pos],b[pos+1]);
                    ++pos;
                }else{
                    ok = 0; break;
                }
            }
        }
        if(is_sorted(ALL(b)) && ok==1) cout << 1; else cout << 0; cout << endl;
    }
}

void solve(){
    cin >> n >> q;
    REP(i,1,n) cin >> a[i];
    if(n<=500 && q<=500){
        sub1(); return ;
    }
    sub1();
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }
    int test = 1;
    while(test--){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 22 ms 604 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 14 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 22 ms 604 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 217 ms 344 KB Output is correct
12 Correct 1835 ms 864 KB Output is correct
13 Correct 2083 ms 888 KB Output is correct
14 Execution timed out 3047 ms 852 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3019 ms 10172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 3416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 22 ms 604 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 217 ms 344 KB Output is correct
12 Correct 1835 ms 864 KB Output is correct
13 Correct 2083 ms 888 KB Output is correct
14 Execution timed out 3047 ms 852 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 22 ms 604 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 217 ms 344 KB Output is correct
12 Correct 1835 ms 864 KB Output is correct
13 Correct 2083 ms 888 KB Output is correct
14 Execution timed out 3047 ms 852 KB Time limit exceeded
15 Halted 0 ms 0 KB -