oj.uz

답안 #874281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874281 2023-11-16T15:40:23 Z Requiem Examination (JOI19_examination) C++17
0 / 100
 3000 ms 419184 KB 
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#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 = 120005;
const int block = 316;
const int MAXBLOCK = 320;
int n,q,x,start,b,RealIndex,res=0;
iv score[MAXN], original[MAXN];
int BIT[330][5*MAXN],prep[MAXN],rev[MAXN],cnt[MAXN],answer[MAXN],complexity;
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){
    res = 0;
    for(int i=id;i<=listval.size();i+=i&(-i)){
        res += BIT[block][i];
    }
    return res;
}
int bs(int l,int r,int x){
    res = r+1;
    while(l<=r){
        int mid = (l+r)>>1;
        if (original[mid].se.fi >= x){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return res;
}
void fastscan(int &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    // extract current character from buffer
    c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;

        // extract the next character from the buffer
        c = getchar();
    }

    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;

    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}

main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    fastscan(n);
    fastscan(q);
    for(int i=1;i<=n;i++){
//        cin>>score[i].se.fi>>score[i].se.se;
        fastscan(score[i].se.fi);
        fastscan(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;
        fastscan(x);
        fastscan(y);
        fastscan(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];
    }
    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<=n;i++){
        prep[i] = i / block;
    }
    int 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 = bs(1,n,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]++;
            }
            complexity++;
            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;
            complexity++;
            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: In function 'int get(int, int)':
examination.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=id;i<=listval.size();i+=i&(-i)){
      |                  ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void fastscan(int&)':
examination.cpp:59:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   59 |     register int c;
      |                  ^
examination.cpp: At global scope:
examination.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main()
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:146: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]
  146 |     for(int i=0;i<query.size();i++){
      |                 ~^~~~~~~~~~~~~
examination.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.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(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 10 ms 27228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1987 ms 226140 KB Output is correct
2 Correct 1922 ms 226744 KB Output is correct
3 Correct 1785 ms 355836 KB Output is correct
4 Correct 648 ms 326604 KB Output is correct
5 Correct 1659 ms 412988 KB Output is correct
6 Correct 225 ms 358716 KB Output is correct
7 Execution timed out 3027 ms 419184 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1987 ms 226140 KB Output is correct
2 Correct 1922 ms 226744 KB Output is correct
3 Correct 1785 ms 355836 KB Output is correct
4 Correct 648 ms 326604 KB Output is correct
5 Correct 1659 ms 412988 KB Output is correct
6 Correct 225 ms 358716 KB Output is correct
7 Execution timed out 3027 ms 419184 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 10 ms 27228 KB Output isn't correct
8 Halted 0 ms 0 KB -