oj.uz

답안 #874450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874450 2023-11-17T04:10:01 Z Requiem Examination (JOI19_examination) C++17
2 / 100
 1393 ms 236832 KB 
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
//#define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define INF 1e18
#define fi first
#define se second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define pi 3.14159265359
#define TASKNAME "examination"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 1e5+9;
const int block = 415;
const int MAXBLOCK = MAXN/block;
int n,q,x,start,b,bitres,bsres,RealIndex;
iv score[MAXN], original[MAXN];
int BIT[330][6*MAXN],nxt[6*MAXN],prep[MAXN],rev[MAXN],cnt[MAXN],answer[MAXN];
vector<int> listval;
vector<iv> query;
void upd(int block,int id,int x){
    for(int i=id;i>0;i-=i&(-i)){
        BIT[block][i] += x;
    }
}
int get(int block,int id){
    bitres = 0;
    for(int i=id;i<=listval.size();i+=i&(-i)){
        bitres += BIT[block][i];
    }
    return bitres;
}
int bs(int l,int r,int x){
    bsres = r+1;
    while(l<=r){
        int mid = (l+r)>>1;
        if (original[mid].se.fi >= x){
            bsres = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return bsres;
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>score[i].se.fi>>score[i].se.se;
        score[i].fi.se = score[i].se.fi + score[i].se.se;
        listval.pb(score[i].se.fi);
        listval.pb(score[i].se.se);
        listval.pb(score[i].fi.se);
    }
    sort(score+1,score+1+n,[](const iv &a,const iv &b){
         return a.se.fi < b.se.fi;
    });

    for(int i=1;i<=q;i++){
        int x,y,z;
        cin>>x>>y>>z;
        listval.pb(x);
        listval.pb(y);
        listval.pb(z);
        query.pb({{i,x},{y,z}});
    }
    sort(listval.begin(),listval.end());
    listval.erase(unique(listval.begin(),listval.end()),listval.end());
    for(int i=1;i<=max(q,n);i++){
        if (i<=n){
            score[i].se.fi = lower_bound(all(listval),score[i].se.fi) - listval.begin() + 1;
            score[i].se.se = lower_bound(all(listval),score[i].se.se) - listval.begin() + 1;
            score[i].fi.se = lower_bound(all(listval),score[i].fi.se) - listval.begin() + 1;
        }
        if (i<=q){
            query[i-1].se.fi = lower_bound(all(listval),query[i-1].se.fi) - listval.begin() + 1;
            query[i-1].se.se = lower_bound(all(listval),query[i-1].se.se) - listval.begin() + 1;
            query[i-1].fi.se = lower_bound(all(listval),query[i-1].fi.se) - listval.begin() + 1;
        }
    }
    for(int i=1;i<=n;i++){
        score[i].fi.fi = i;
        original[i] = score[i];
    }
    int ptr = 1;
    for(int i=1;i<=listval.size();i++){
        while(ptr <= n and original[ptr].se.fi < i){
            ptr++;
        }
        if (ptr<=n) nxt[i] = original[ptr].fi.fi;
        else nxt[i] = n+1;
    }
    sort(query.begin(),query.end(),[](const iv &a,const iv &b){
         return a.se.se > b.se.se;
    });
    sort(score+1,score+1+n,[](const iv &a,const iv &b){
         return a.fi.se > b.fi.se;
    });
    for(int i=1;i<MAXN;i++){
        prep[i] = i / block;
    }
    ptr = 1;
    for(int i=0;i<query.size();i++){
        while(ptr <= n and score[ptr].fi.se >= query[i].se.se){
            RealIndex = score[ptr].fi.fi;
            rev[RealIndex]++;
            b = prep[RealIndex];
            cnt[b]++;

            upd(b,score[ptr].se.se,1);
            ptr++;
        }
        start = nxt[query[i].fi.se];
        b = prep[start];
        for(int j=start;j<=n;j++){
            if (original[j].se.fi >= query[i].fi.se and
                original[j].se.se >= query[i].se.fi and
                original[j].fi.se >= query[i].se.se and
                rev[j] > 0){
                    answer[query[i].fi.fi]++;
            }
            if (prep[j] != prep[j+1]) {
                break;
            }
        }

        for(int cur=b+1;cur<MAXBLOCK;cur++){
            if (cur * block > n) break;
            if (cnt[cur] == 0) continue;
            answer[query[i].fi.fi] += get(cur,query[i].se.fi);
        }

    }
    for(int i=1;i<=q;i++){
        cout<<answer[i]<<endl;
    }
}

Compilation message

examination.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("Ofast")
      | 
examination.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      | 
examination.cpp: In function 'int get(int, int)':
examination.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=id;i<=listval.size();i+=i&(-i)){
      |                  ~^~~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main()
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=1;i<=listval.size();i++){
      |                 ~^~~~~~~~~~~~~~~~
examination.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0;i<query.size();i++){
      |                 ~^~~~~~~~~~~~~
examination.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 10 ms 23132 KB Output is correct
8 Correct 10 ms 23132 KB Output is correct
9 Correct 10 ms 23132 KB Output is correct
10 Correct 8 ms 23264 KB Output is correct
11 Correct 9 ms 23128 KB Output is correct
12 Correct 8 ms 23132 KB Output is correct
13 Correct 9 ms 23132 KB Output is correct
14 Correct 9 ms 23128 KB Output is correct
15 Correct 9 ms 23132 KB Output is correct
16 Correct 8 ms 23276 KB Output is correct
17 Correct 7 ms 23132 KB Output is correct
18 Correct 4 ms 23268 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1393 ms 236832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1393 ms 236832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 10 ms 23132 KB Output is correct
8 Correct 10 ms 23132 KB Output is correct
9 Correct 10 ms 23132 KB Output is correct
10 Correct 8 ms 23264 KB Output is correct
11 Correct 9 ms 23128 KB Output is correct
12 Correct 8 ms 23132 KB Output is correct
13 Correct 9 ms 23132 KB Output is correct
14 Correct 9 ms 23128 KB Output is correct
15 Correct 9 ms 23132 KB Output is correct
16 Correct 8 ms 23276 KB Output is correct
17 Correct 7 ms 23132 KB Output is correct
18 Correct 4 ms 23268 KB Output is correct
19 Incorrect 1393 ms 236832 KB Output isn't correct
20 Halted 0 ms 0 KB -