제출 #329749

#제출 시각아이디문제언어결과실행 시간메모리
329749figter001팀들 (IOI15_teams)C++17
0 / 100
2503 ms190960 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define fast ios::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int nax = 5e5 + 100; struct node{ int l,r; ll sum; node(){ l = r = -1; sum = 0; } }seg[22*nax]; ll head[nax]; int T; void update(int n,int s,int e,int at,int val,int old){ if(s == e){ // cerr << n << ' ' << old << ' ' << seg[old].sum << '\n'; seg[n].sum += seg[old].sum + val; return; } if((s+e)/2 < at)seg[n].l = seg[old].l; else{ seg[n].l = ++T; update(seg[n].l,s,(s+e)/2,at,val,seg[old].l); } if((s+e)/2+1 > at)seg[n].r = seg[old].r; else{ seg[n].r = ++T; update(seg[n].r,(s+e)/2+1,e,at,val,seg[old].r); } seg[n].sum = seg[ seg[n].l ].sum + seg[ seg[n].r ].sum; // cerr << seg[n].sum << ' ' << s << ' ' << e << '\n'; } ll get(int n,int s,int e,int l,int r){ if(n <= 0)return 0; // assert(n >0); if(s > r || e < l || l > r)return 0; if(s >= l && e <= r)return seg[n].sum; return get( seg[n].l , s , (s+e)/2 , l , r ) + get( seg[n].r , (s+e)/2+1 , e , l , r); } // int main(){ // int cur = 1; // head[cur] = ++T; // build(head[1],1,n); // for(int i=0;i<q;i++){ // int t,k; // cin>>t>>k; // if(t == 1){//update // int at,val; // cin>>at>>val; // int old = head[k]; // head[k] = ++T; // update(head[k],1,n,at,val,old); // }else if(t == 2){//sum // int l,r; // cin>>l>>r; // cout << get(head[k],1,n,l,r) << endl; // }else if(t == 3){//make new // cur++; // head[cur] = head[k]; // } // } // } vector<pair<int,int>> s; int n; void init(int N, int A[], int B[]) { n = N; for(int i=0;i<n;i++)s.push_back({A[i], B[i]}); sort(all(s)); head[0] = ++T; int lst = T; for(int i=0;i<n;i++){ head[s[i].first] = ++T; update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst); // cerr << ' ' << head[s[i].first] << ' ' << lst << ' ' << get(head[s[i].first],1,n,1,n) << '\n'; lst = head[s[i].first]; } for(int i=1;i<=n;i++){ if(head[i] == 0) head[i] = head[i-1]; } } int can(int M, int K[]) { // return 0; sort(K,K+M); int ex = 0; int lst = 0; multiset<pair<int,int>> k; int id = 0; for(int i=0;i<M;i++){ while(k.size() && k.begin()->first <= K[i]){ ex -= k.begin()->second; k.erase(k.begin()); } // cerr << K[i] << ' ' << ex << ' ' << get(head[K[i]],1,n,K[i] , n) << '\n'; ex += K[i]; if(get(head[K[i]],1,n,K[i] , n) < ex){ // cerr << 0 << ' '; return 0; } int lo=K[i],hi = n,to=n; while(lo <= hi){ int md = (lo + hi)/2; if(get(head[K[i]] , 1 , n , K[i] , md) > ex){ hi = md-1; to = md; }else{ lo = md + 1; } } k.insert({to , K[i]}); // if(k[id] != K[i])return 0; } // cerr << 1 << ' '; return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:91:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |                                                     ~~~~~~~~^
teams.cpp:91:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |          ~~~~~~~~~~~~~~~^
teams.cpp:91:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |                                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:93:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |   lst = head[s[i].first];
      |         ~~~~~~~~~~~~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:115:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |   if(get(head[K[i]],1,n,K[i] , n) < ex){
      |          ~~~~~~~~~^
teams.cpp:122:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |    if(get(head[K[i]] , 1 , n , K[i] , md) > ex){
      |           ~~~~~~~~~^
teams.cpp:105:6: warning: unused variable 'lst' [-Wunused-variable]
  105 |  int lst = 0;
      |      ^~~
teams.cpp:107:6: warning: unused variable 'id' [-Wunused-variable]
  107 |  int id = 0;
      |      ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...