oj.uz

답안 #957395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957395 2024-04-03T15:58:55 Z YassirSalama Two Currencies (JOI23_currencies) C++17
30 / 100
 1892 ms 76280 KB 
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
int BIT[MAXN];
int BIT2[MAXN];
void init(){
    // for(int i=0;i<MAXN;i++) BIT[i]=0;
    memset(BIT,0,sizeof(BIT));
    memset(BIT2,0,sizeof(BIT2));
}
void add(int i,int x){
    i++;
    while(i<MAXN){
        BIT[i]+=x;
        i+=i&-i;
    }
}
void add2(int i,int x){
    i++;
    while(i<MAXN){
        BIT[i]+=x;
        BIT2[i]++;
        i+=i&-i;
    }
}
int s2(int i){
    i++;
    int ans=0;
    while(i){
        ans+=BIT2[i];
        i-=i&-i;
    }
    return ans;
}
int s(int i){
    i++;
    int ans=0;
    while(i){
        ans+=BIT[i];
        i-=i&-i;
    }
    return ans;
}
int q(int l,int r){
    if(l>r) return 0LL;
    if(l==0) return s(r);
    return s(r)-s(l-1);
}  
int q2(int l,int r){
    if(l>r) return 0LL;
    if(l==0) return s2(r);
    return s2(r)-s2(l-1);
}  
int pref1[MAXN];
int pref2[MAXN];

signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m,Q;
cin>>n>>m>>Q;
vector<pair<int,int>> edges;
for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    edges.pb({a,b});
}
vector<tuple<int,int,int>> ed;
ed.pb({0,0,0});
for(int i=0;i<m;i++){
    int p,c;
    cin>>p>>c;
    p--;
    auto [a,b]=edges[p];
    ed.pb({c,a,b});
}
sort(all(ed));
auto up = [&](int i,int x){
    i++;
    pref1[i]+=x;
    pref2[i]++;
};
auto s1=[&](int l,int r){
    l++,r++;
    if(l>r) return 0LL;
    if(l==0) return pref1[r];
    return pref1[r]-pref1[l-1];
};
auto ss2 = [&](int l,int r){
    l++,r++;
    if(l>r) return 0LL;
    if(l==0) return pref2[r];
    else return pref2[r]-pref2[l-1];
};
for(int i=0;i<=m;i++){
    auto [c,a,b]=ed[i];
    up(a,c);
}
for(int i=1;i<MAXN;i++){
    pref1[i]+=pref1[i-1];
    pref2[i]+=pref2[i-1];
}
vector<vector<int>> queries;
for(int i=0;i<Q;i++){
    int s,t,x,y;
    cin>>s>>t>>x>>y;
    if(s>t) swap(s,t);
    queries.pb({m/2,0,m,s,t,x,y,i});
}
vector<vector<int>> cc=queries;
int ans[Q];
memset(ans,0,sizeof(ans));
while(true){
    init();
    vector<vector<int>> cp=queries;
    sort(all(queries));
    vector<vector<int>> ndone;
    for(auto x:queries){
        if(x[1]>x[2]) {
            continue;
        }
        else ndone.pb(x);
    }
    queries=ndone;
    if(queries.empty()) break;
    sort(all(queries));
    vector<vector<int>> c[m+1];
    for(auto x:queries){
        c[x[0]].pb(x);
    }
    for(int i=0;i<=m;i++){
        auto [d,a,b]=ed[i];
        add(a,d);
        for(auto x:c[i]){
            int a=x[3],b=x[4];
            int f=q(a,b-1);
            if(f<=x[6]){
                ans[x[7]]=i;
                cp[x[7]][1]=i+1;
                cp[x[7]][0]=(cp[x[7]][1]+cp[x[7]][2])/2;
            }else{
                cp[x[7]][2]=i-1;
                cp[x[7]][0]=(cp[x[7]][1]+cp[x[7]][2])/2;                
            }
        }
    }
    queries=cp;
}
queries=cc;
vector<vector<int>> c[m+1];
for(auto x:queries){
    c[ans[x[7]]].pb(x);
}
int dans[Q+1];
memset(dans,0,sizeof(dans));
init();
for(int i=0;i<=m;i++){
    auto [d,a,b]=ed[i];
    add2(a,d);
    for(auto t:c[i]){
        int a=t[3],b=t[4];
        int e=q2(a,b-1); 
        int x=t[5],y=t[6],j=t[7];
        int ee=ss2(a,b-1);
        ee-=e;
        if(x>=ee){
            dans[j]=x-ee;
        }else dans[j]=-1;
    }

}
for(int i=0;i<Q;i++){
    cout<<dans[i]<<endl;
}
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:179:20: warning: unused variable 'y' [-Wunused-variable]
  179 |         int x=t[5],y=t[6],j=t[7];
      |                    ^
currencies.cpp:99:6: warning: variable 's1' set but not used [-Wunused-but-set-variable]
   99 | auto s1=[&](int l,int r){
      |      ^~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 28.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 15 ms 7912 KB Output is correct
3 Correct 13 ms 7772 KB Output is correct
4 Correct 14 ms 7772 KB Output is correct
5 Correct 983 ms 50556 KB Output is correct
6 Correct 957 ms 54432 KB Output is correct
7 Correct 1447 ms 66908 KB Output is correct
8 Correct 1808 ms 76280 KB Output is correct
9 Correct 1746 ms 73488 KB Output is correct
10 Correct 1821 ms 76204 KB Output is correct
11 Correct 1734 ms 75976 KB Output is correct
12 Correct 1742 ms 74500 KB Output is correct
13 Correct 1892 ms 73304 KB Output is correct
14 Correct 1816 ms 75544 KB Output is correct
15 Correct 1825 ms 73484 KB Output is correct
16 Correct 1763 ms 73764 KB Output is correct
17 Correct 1763 ms 75920 KB Output is correct

Subtask #4
0 / 32.0

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